A 2-connected graph contains a path passing through all the odd degree verticesIf given the girth and the minimum degree of a simple graph $G$, can we give a lower bound on the number of vertices it has?Connected graphs, Euler circuits and paths, vertices of odd degreeProve: Graph in which every pair of vertices has an odd number of common neighbors is Eulerian.Prove that every connected graph whose vertices are all of even degree has no cut-verticesAn example of connected graph with vertices having at least 3 degree, but non-hamiltonian?Prove the existence of a graph of 15 vertices with some vertices degree givenEulerian Graph with odd number of verticesA Hamiltonian graph contains at least two vertices of degree $geq 3$All vertices except $d+1$ have degree at most $d$, then it is ($d+1$)-colorable.Let $G$ be a connected graph with $n>=3$ vertices.
Does the talk count as invited if my PI invited me?
Pedaling at different gear ratios on flat terrain: what's the point?
Can I modify the report menu?
Windows reverting changes made by Linux to FAT32 partion
What color to choose as "danger" if the main color of my app is red
Error when running ((x++)) as root
FIFO data structure in pure C
Can Gate draw a creature larger that 20 feet in every dimension through the portal it creates?
Cathy’s Composite party is powered by three Prime Pals. Can you find them?
How to customize the pie chart background in PowerPoint?
Lock out of Oracle based on Windows username
Can 2 light bulbs of 120V in series be used on 230V AC?
Why aren't satellites disintegrated even though they orbit earth within earth's Roche Limits?
Why didn't Daenerys' advisers suggest assassinating Cersei?
Should all adjustments be random effects in a mixed linear effect?
Told to apply for UK visa before other visas
Why does string strummed with finger sound different from the one strummed with pick?
Gaussian kernel density estimation with data from file
Good examples of "two is easy, three is hard" in computational sciences
Why use a retrograde orbit?
Using `printf` to print variable containing `%` percent sign results in "bash: printf: `p': invalid format character"
How can I monitor the bulk API limit?
Why would company (decision makers) wait for someone to retire, rather than lay them off, when their role is no longer needed?
Why does a table with a defined constant in its index compute 10X slower?
A 2-connected graph contains a path passing through all the odd degree vertices
If given the girth and the minimum degree of a simple graph $G$, can we give a lower bound on the number of vertices it has?Connected graphs, Euler circuits and paths, vertices of odd degreeProve: Graph in which every pair of vertices has an odd number of common neighbors is Eulerian.Prove that every connected graph whose vertices are all of even degree has no cut-verticesAn example of connected graph with vertices having at least 3 degree, but non-hamiltonian?Prove the existence of a graph of 15 vertices with some vertices degree givenEulerian Graph with odd number of verticesA Hamiltonian graph contains at least two vertices of degree $geq 3$All vertices except $d+1$ have degree at most $d$, then it is ($d+1$)-colorable.Let $G$ be a connected graph with $n>=3$ vertices.
$begingroup$
I am trying to prove the above as an exercise in the topic of connectivity. I have tried to do so using ear decompositions, as odd degree vertices may be characterized as end points of ears, but to no avail. Any recommendations are appreciated.
Thanks
discrete-mathematics graph-theory graph-connectivity
asked May 5 at 22:54
ChristianHollisChristianHollis
282
$endgroup$
add a comment |
$begingroup$
I am trying to prove the above as an exercise in the topic of connectivity. I have tried to do so using ear decompositions, as odd degree vertices may be characterized as end points of ears, but to no avail. Any recommendations are appreciated.
Thanks
discrete-mathematics graph-theory graph-connectivity
asked May 5 at 22:54
ChristianHollisChristianHollis
282
$endgroup$
add a comment |
$begingroup$
I am trying to prove the above as an exercise in the topic of connectivity. I have tried to do so using ear decompositions, as odd degree vertices may be characterized as end points of ears, but to no avail. Any recommendations are appreciated.
Thanks
discrete-mathematics graph-theory graph-connectivity
asked May 5 at 22:54
ChristianHollisChristianHollis
282
$endgroup$
I am trying to prove the above as an exercise in the topic of connectivity. I have tried to do so using ear decompositions, as odd degree vertices may be characterized as end points of ears, but to no avail. Any recommendations are appreciated.
Thanks
discrete-mathematics graph-theory graph-connectivity
discrete-mathematics graph-theory graph-connectivity
asked May 5 at 22:54
ChristianHollisChristianHollis
282
asked May 5 at 22:54
ChristianHollisChristianHollis
282
asked May 5 at 22:54
ChristianHollisChristianHollis
282
asked May 5 at 22:54
ChristianHollisChristianHollis
282
asked May 5 at 22:54
ChristianHollisChristianHollis
282
282
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
The statement is false. Take the following $5$-regular graph (inspired by the graph in this MathOverflow answer, which being $4$-regular didn't quite do the trick):
In this graph, every degree is odd, so we are looking for a Hamiltonian path. However, to visit each of the five parts around the sides, we would have to go through the middle vertices multiple times, so this is impossible.
For a slightly more formal argument: if a graph $G$ has a Hamiltonian path, it has a path $P_n$ as a subgraph. Deleting two vertices from $P_n$ leaves at most $3$ components, so the same must be true of $G$ (which is $P_n$ with extra edges). But in the graph above, deleting the two middle vertices leaves $5$ components, so it can't have a Hamiltonian path.
answered May 6 at 0:02
Misha LavrovMisha Lavrov
51.5k761112
$endgroup$
$begingroup$
Maybe I’m missing something, but it looks like every vertex has degree four, and the question as it appears now is about paths that go through every odd-degree vertex. There are no such vertices in your graph. The Thomassen graphs here might be the example needed: mathworld.wolfram.com/ThomassenGraphs.html (oops, not, I think now...)
$endgroup$
– Steve Kass
May 6 at 0:23
1
$begingroup$
Whoops - the MathOverflow question was about all $k$-regular graphs for $k=3$, so naturally this graph uses $k=4$ rather than $k=5$... I will fix this.
$endgroup$
– Misha Lavrov
May 6 at 0:27
1
$begingroup$
(+1) Because the claim doesn't assume regularity, you can get a smaller (and planar!) counterexample by taking five $K_4$s rather than five $K_6$s.
$endgroup$
– Henning Makholm
May 6 at 1:06
$begingroup$
@HenningMakholm We could even take only four $K_4$s rather than five; then we wouldn't need to visit both cut vertices, but that's not the obstacle to begin with...
$endgroup$
– Misha Lavrov
May 6 at 1:10
add a comment |
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3215190%2fa-2-connected-graph-contains-a-path-passing-through-all-the-odd-degree-vertices%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The statement is false. Take the following $5$-regular graph (inspired by the graph in this MathOverflow answer, which being $4$-regular didn't quite do the trick):
In this graph, every degree is odd, so we are looking for a Hamiltonian path. However, to visit each of the five parts around the sides, we would have to go through the middle vertices multiple times, so this is impossible.
For a slightly more formal argument: if a graph $G$ has a Hamiltonian path, it has a path $P_n$ as a subgraph. Deleting two vertices from $P_n$ leaves at most $3$ components, so the same must be true of $G$ (which is $P_n$ with extra edges). But in the graph above, deleting the two middle vertices leaves $5$ components, so it can't have a Hamiltonian path.
answered May 6 at 0:02
Misha LavrovMisha Lavrov
51.5k761112
$endgroup$
$begingroup$
Maybe I’m missing something, but it looks like every vertex has degree four, and the question as it appears now is about paths that go through every odd-degree vertex. There are no such vertices in your graph. The Thomassen graphs here might be the example needed: mathworld.wolfram.com/ThomassenGraphs.html (oops, not, I think now...)
$endgroup$
– Steve Kass
May 6 at 0:23
1
$begingroup$
Whoops - the MathOverflow question was about all $k$-regular graphs for $k=3$, so naturally this graph uses $k=4$ rather than $k=5$... I will fix this.
$endgroup$
– Misha Lavrov
May 6 at 0:27
1
$begingroup$
(+1) Because the claim doesn't assume regularity, you can get a smaller (and planar!) counterexample by taking five $K_4$s rather than five $K_6$s.
$endgroup$
– Henning Makholm
May 6 at 1:06
$begingroup$
@HenningMakholm We could even take only four $K_4$s rather than five; then we wouldn't need to visit both cut vertices, but that's not the obstacle to begin with...
$endgroup$
– Misha Lavrov
May 6 at 1:10
add a comment |
$begingroup$
The statement is false. Take the following $5$-regular graph (inspired by the graph in this MathOverflow answer, which being $4$-regular didn't quite do the trick):
In this graph, every degree is odd, so we are looking for a Hamiltonian path. However, to visit each of the five parts around the sides, we would have to go through the middle vertices multiple times, so this is impossible.
For a slightly more formal argument: if a graph $G$ has a Hamiltonian path, it has a path $P_n$ as a subgraph. Deleting two vertices from $P_n$ leaves at most $3$ components, so the same must be true of $G$ (which is $P_n$ with extra edges). But in the graph above, deleting the two middle vertices leaves $5$ components, so it can't have a Hamiltonian path.
answered May 6 at 0:02
Misha LavrovMisha Lavrov
51.5k761112
$endgroup$
$begingroup$
Maybe I’m missing something, but it looks like every vertex has degree four, and the question as it appears now is about paths that go through every odd-degree vertex. There are no such vertices in your graph. The Thomassen graphs here might be the example needed: mathworld.wolfram.com/ThomassenGraphs.html (oops, not, I think now...)
$endgroup$
– Steve Kass
May 6 at 0:23
1
$begingroup$
Whoops - the MathOverflow question was about all $k$-regular graphs for $k=3$, so naturally this graph uses $k=4$ rather than $k=5$... I will fix this.
$endgroup$
– Misha Lavrov
May 6 at 0:27
1
$begingroup$
(+1) Because the claim doesn't assume regularity, you can get a smaller (and planar!) counterexample by taking five $K_4$s rather than five $K_6$s.
$endgroup$
– Henning Makholm
May 6 at 1:06
$begingroup$
@HenningMakholm We could even take only four $K_4$s rather than five; then we wouldn't need to visit both cut vertices, but that's not the obstacle to begin with...
$endgroup$
– Misha Lavrov
May 6 at 1:10
add a comment |
$begingroup$
The statement is false. Take the following $5$-regular graph (inspired by the graph in this MathOverflow answer, which being $4$-regular didn't quite do the trick):
In this graph, every degree is odd, so we are looking for a Hamiltonian path. However, to visit each of the five parts around the sides, we would have to go through the middle vertices multiple times, so this is impossible.
For a slightly more formal argument: if a graph $G$ has a Hamiltonian path, it has a path $P_n$ as a subgraph. Deleting two vertices from $P_n$ leaves at most $3$ components, so the same must be true of $G$ (which is $P_n$ with extra edges). But in the graph above, deleting the two middle vertices leaves $5$ components, so it can't have a Hamiltonian path.
answered May 6 at 0:02
Misha LavrovMisha Lavrov
51.5k761112
$endgroup$
The statement is false. Take the following $5$-regular graph (inspired by the graph in this MathOverflow answer, which being $4$-regular didn't quite do the trick):
In this graph, every degree is odd, so we are looking for a Hamiltonian path. However, to visit each of the five parts around the sides, we would have to go through the middle vertices multiple times, so this is impossible.
For a slightly more formal argument: if a graph $G$ has a Hamiltonian path, it has a path $P_n$ as a subgraph. Deleting two vertices from $P_n$ leaves at most $3$ components, so the same must be true of $G$ (which is $P_n$ with extra edges). But in the graph above, deleting the two middle vertices leaves $5$ components, so it can't have a Hamiltonian path.
answered May 6 at 0:02
Misha LavrovMisha Lavrov
51.5k761112
edited May 6 at 0:49
answered May 6 at 0:02
Misha LavrovMisha Lavrov
51.5k761112
answered May 6 at 0:02
Misha LavrovMisha Lavrov
51.5k761112
answered May 6 at 0:02
Misha LavrovMisha Lavrov
51.5k761112
51.5k761112
$begingroup$
Maybe I’m missing something, but it looks like every vertex has degree four, and the question as it appears now is about paths that go through every odd-degree vertex. There are no such vertices in your graph. The Thomassen graphs here might be the example needed: mathworld.wolfram.com/ThomassenGraphs.html (oops, not, I think now...)
$endgroup$
– Steve Kass
May 6 at 0:23
1
$begingroup$
Whoops - the MathOverflow question was about all $k$-regular graphs for $k=3$, so naturally this graph uses $k=4$ rather than $k=5$... I will fix this.
$endgroup$
– Misha Lavrov
May 6 at 0:27
1
$begingroup$
(+1) Because the claim doesn't assume regularity, you can get a smaller (and planar!) counterexample by taking five $K_4$s rather than five $K_6$s.
$endgroup$
– Henning Makholm
May 6 at 1:06
$begingroup$
@HenningMakholm We could even take only four $K_4$s rather than five; then we wouldn't need to visit both cut vertices, but that's not the obstacle to begin with...
$endgroup$
– Misha Lavrov
May 6 at 1:10
add a comment |
$begingroup$
Maybe I’m missing something, but it looks like every vertex has degree four, and the question as it appears now is about paths that go through every odd-degree vertex. There are no such vertices in your graph. The Thomassen graphs here might be the example needed: mathworld.wolfram.com/ThomassenGraphs.html (oops, not, I think now...)
$endgroup$
– Steve Kass
May 6 at 0:23
1
$begingroup$
Whoops - the MathOverflow question was about all $k$-regular graphs for $k=3$, so naturally this graph uses $k=4$ rather than $k=5$... I will fix this.
$endgroup$
– Misha Lavrov
May 6 at 0:27
1
$begingroup$
(+1) Because the claim doesn't assume regularity, you can get a smaller (and planar!) counterexample by taking five $K_4$s rather than five $K_6$s.
$endgroup$
– Henning Makholm
May 6 at 1:06
$begingroup$
@HenningMakholm We could even take only four $K_4$s rather than five; then we wouldn't need to visit both cut vertices, but that's not the obstacle to begin with...
$endgroup$
– Misha Lavrov
May 6 at 1:10
$begingroup$
Maybe I’m missing something, but it looks like every vertex has degree four, and the question as it appears now is about paths that go through every odd-degree vertex. There are no such vertices in your graph. The Thomassen graphs here might be the example needed: mathworld.wolfram.com/ThomassenGraphs.html (oops, not, I think now...)
$endgroup$
– Steve Kass
May 6 at 0:23
$begingroup$
Maybe I’m missing something, but it looks like every vertex has degree four, and the question as it appears now is about paths that go through every odd-degree vertex. There are no such vertices in your graph. The Thomassen graphs here might be the example needed: mathworld.wolfram.com/ThomassenGraphs.html (oops, not, I think now...)
$endgroup$
– Steve Kass
May 6 at 0:23
1
1
$begingroup$
Whoops - the MathOverflow question was about all $k$-regular graphs for $k=3$, so naturally this graph uses $k=4$ rather than $k=5$... I will fix this.
$endgroup$
– Misha Lavrov
May 6 at 0:27
$begingroup$
Whoops - the MathOverflow question was about all $k$-regular graphs for $k=3$, so naturally this graph uses $k=4$ rather than $k=5$... I will fix this.
$endgroup$
– Misha Lavrov
May 6 at 0:27
1
1
$begingroup$
(+1) Because the claim doesn't assume regularity, you can get a smaller (and planar!) counterexample by taking five $K_4$s rather than five $K_6$s.
$endgroup$
– Henning Makholm
May 6 at 1:06
$begingroup$
(+1) Because the claim doesn't assume regularity, you can get a smaller (and planar!) counterexample by taking five $K_4$s rather than five $K_6$s.
$endgroup$
– Henning Makholm
May 6 at 1:06
$begingroup$
@HenningMakholm We could even take only four $K_4$s rather than five; then we wouldn't need to visit both cut vertices, but that's not the obstacle to begin with...
$endgroup$
– Misha Lavrov
May 6 at 1:10
$begingroup$
@HenningMakholm We could even take only four $K_4$s rather than five; then we wouldn't need to visit both cut vertices, but that's not the obstacle to begin with...
$endgroup$
– Misha Lavrov
May 6 at 1:10
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3215190%2fa-2-connected-graph-contains-a-path-passing-through-all-the-odd-degree-vertices%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
