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.
Has there been evidence of any other gods?
Can a planet still function with a damaged moon?
Which spells are in some way related to shadows or the Shadowfell?
Are wands in any sort of book going to be too much like Harry Potter?
if i accidentally leaked my schools ip address and someone d doses my school am i at fault
"Estrontium" on poster
Rusty Chain and back cassette – Replace or Repair?
Does a surprised creature obey the 1st level spell Command?
Are there vaccine ingredients which may not be disclosed ("hidden", "trade secret", or similar)?
What dice to use in a game that revolves around triangles?
And now you see it II (the B side)
How can Sam Wilson fulfill his future role?
Narcissistic cube asks who are we?
How do I minimise waste on a flight?
Is it a Munchausen Number?
Not taking the bishop with the knight, why?
My perfect evil overlord plan... or is it?
Integral with DiracDelta. Can Mathematica be made to solve this?
Was Mohammed the most popular first name for boys born in Berlin in 2018?
What is the Ancient One's mistake?
Does Thread.yield() do anything if we have enough processors to service all threads?
What are these round pads on the bottom of a PCB?
Has everyone forgotten about wildfire?
Employee is self-centered and affects the team negatively
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
New contributor
ChristianHollis is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$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
New contributor
ChristianHollis is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$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
New contributor
ChristianHollis is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$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
New contributor
ChristianHollis is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked May 5 at 22:54
ChristianHollisChristianHollis
282
New contributor
ChristianHollis is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked May 5 at 22:54
ChristianHollisChristianHollis
282
New contributor
ChristianHollis is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked May 5 at 22:54
ChristianHollisChristianHollis
282
asked May 5 at 22:54
ChristianHollisChristianHollis
282
282
New contributor
ChristianHollis is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
ChristianHollis is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
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.3k761112
$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
);
);
ChristianHollis is a new contributor. Be nice, and check out our Code of Conduct.
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.3k761112
$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.3k761112
$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.3k761112
$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.3k761112
edited May 6 at 0:49
answered May 6 at 0:02
Misha LavrovMisha Lavrov
51.3k761112
answered May 6 at 0:02
Misha LavrovMisha Lavrov
51.3k761112
answered May 6 at 0:02
Misha LavrovMisha Lavrov
51.3k761112
51.3k761112
$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 |
ChristianHollis is a new contributor. Be nice, and check out our Code of Conduct.
ChristianHollis is a new contributor. Be nice, and check out our Code of Conduct.
ChristianHollis is a new contributor. Be nice, and check out our Code of Conduct.
ChristianHollis is a new contributor. Be nice, and check out our Code of Conduct.
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
