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.
Can a good but unremarkable PhD student become an accomplished professor?
What does the phrase "go for the pin" mean here?
GitLab account hacked and repo wiped
How can I finally understand the confusing modal verb "мочь"?
The selling of the sheep
How important are good looking people in a novel/story?
How did the Force make Luke hard to hit in the Battle of Yavin?
Hostile Divisor Numbers
What do you call a painting painted on a wall?
What's the 2-minute timer on mobile Deutsche Bahn tickets?
How is Pauli's exclusion principle still valid in these cases?
How long did it take Captain Marvel to travel to Earth?
All of my Firefox add-ons been disabled suddenly, how can I re-enable them?
How long does it take a postcard to get from USA to Germany?
Where to draw the line between quantum mechanics theory and its interpretation(s)?
How do I, as a DM, handle a party that decides to set up an ambush in a dungeon?
TIP120 Transistor + Solenoid Failing Randomly
Dimmer switch not connected to ground
Do Jedi mind tricks work on Ewoks?
Antivirus for Ubuntu 18.04
Can anyone identify this unknown 1988 PC card from The Palantir Corporation?
What are the requirements for a river delta to form?
What is a common way to tell if an academic is "above average," or outstanding in their field? Is their h-index (Hirsh index) one of them?
Why can't argument be forwarded inside lambda without mutable?
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 2 hours ago
ChristianHollisChristianHollis
132
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 2 hours ago
ChristianHollisChristianHollis
132
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 2 hours ago
ChristianHollisChristianHollis
132
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 2 hours ago
ChristianHollisChristianHollis
132
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 2 hours ago
ChristianHollisChristianHollis
132
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 2 hours ago
ChristianHollisChristianHollis
132
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 2 hours ago
ChristianHollisChristianHollis
132
asked 2 hours ago
ChristianHollisChristianHollis
132
132
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.
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 1 hour ago
Misha LavrovMisha Lavrov
51.2k760110
$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
1 hour ago
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
1 hour ago
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
31 mins ago
$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
27 mins ago
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 1 hour ago
Misha LavrovMisha Lavrov
51.2k760110
$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
1 hour ago
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
1 hour ago
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
31 mins ago
$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
27 mins ago
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 1 hour ago
Misha LavrovMisha Lavrov
51.2k760110
$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
1 hour ago
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
1 hour ago
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
31 mins ago
$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
27 mins ago
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 1 hour ago
Misha LavrovMisha Lavrov
51.2k760110
$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 1 hour ago
Misha LavrovMisha Lavrov
51.2k760110
edited 47 mins ago
answered 1 hour ago
Misha LavrovMisha Lavrov
51.2k760110
answered 1 hour ago
Misha LavrovMisha Lavrov
51.2k760110
answered 1 hour ago
Misha LavrovMisha Lavrov
51.2k760110
51.2k760110
$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
1 hour ago
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
1 hour ago
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
31 mins ago
$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
27 mins ago
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
1 hour ago
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
1 hour ago
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
31 mins ago
$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
27 mins ago
$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
1 hour ago
$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
1 hour ago
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
1 hour ago
$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
1 hour ago
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
31 mins ago
$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
31 mins ago
$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
27 mins ago
$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
27 mins ago
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
