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.
What is monoid homomorphism exactly?
Antivirus for Ubuntu 18.04
How is trade in services conducted under the WTO in the absence of the Doha conclusion?
My large rocket is still flipping over
As a GM, is it bad form to ask for a moment to think when improvising?
Is throwing dice a stochastic or a deterministic process?
What would happen if I combined this polymer and this metal (assuming I can)
Picking a theme as a discovery writer
Is there a reason why Turkey took the Balkan territories of the Ottoman Empire, instead of Greece or another of the Balkan states?
What's the 2-minute timer on mobile Deutsche Bahn tickets?
How would you say "You forget wearing what you're wearing"?
Referring to person by surname, keep or omit "von"?
Installing Debian 10, upgrade to stable later?
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?
Problem with estimating a sequence with intuition
hl with custom color and linebreak and math
Primes in a Diamond
HSA - Continue to Invest?
Playing Doublets with the Primes
Hostile Divisor Numbers
Copper as an adjective to refer to something made of copper
A 2-connected graph contains a path passing through all the odd degree vertices
Can I combine SELECT TOP() with the IN operator?
Subnumcases as a part of align
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
32 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
28 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
32 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
28 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
32 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
28 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 48 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
32 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
28 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
32 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
28 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
32 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
32 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
28 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
28 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
