All 4-connected planar graphs are Hamiltonian-connected
$begingroup$
I started reading Thomassen's paper A Theorem on Paths in Planar Graphs, where he proves one of Plummer's conjectures: Every $4$-connected planar graph is Hamiltonian-connected.
Context. Recall that a graph $G$ is called Hamiltonian-connected if for every two vertices $x$ and $y$ in $G$, we can find a Hamiltonian path starting from $x$ and ending at $y$. This is a rather strong condition, and in particular implies that $G$ must have a Hamiltonian circuit (indeed, we can take two adjacent vertices $x$ and $y$, find a Hamiltonian path from $y$ to $x$, and then add the edge $xy$ back to get a Hamiltonian circuit). In particular, Plummer's conjecture already implies Tutte's celebrated theorem that every $4$-connected planar graph is Hamiltonian (i.e. contains a Hamiltonian circuit).
For my question below to make sense, it also helps to be familiar with the definition of $H$-component where $H$ is a subgraph of $G$. Here is the definition, taken from Thomassen's paper:
Finally, an outer cycle just means the cycle bounding the outside (infinite) face of a planar graph in its plane drawing. With all the definitions out of the way, Thomassen's main theorem is the following:
Thomassen claims that the theorem above immediately implies
Plummer's conjecture: Every $4$-connected planar graph is Hamiltonian-connected.
My question is: Can somebody explain how to see this implication? I presume that we need to remove two points $x$ and $y$, which would result in a $2$-connected graph. After that, do we apply the Theorem above? But it is not clear to me what the vertex $u$ or the edge $e$ should be. I would very much appreciate if someone could elaborate and explain the details. Thanks!
graph-theory proof-explanation planar-graph hamiltonian-path
$endgroup$
add a comment |
$begingroup$
I started reading Thomassen's paper A Theorem on Paths in Planar Graphs, where he proves one of Plummer's conjectures: Every $4$-connected planar graph is Hamiltonian-connected.
Context. Recall that a graph $G$ is called Hamiltonian-connected if for every two vertices $x$ and $y$ in $G$, we can find a Hamiltonian path starting from $x$ and ending at $y$. This is a rather strong condition, and in particular implies that $G$ must have a Hamiltonian circuit (indeed, we can take two adjacent vertices $x$ and $y$, find a Hamiltonian path from $y$ to $x$, and then add the edge $xy$ back to get a Hamiltonian circuit). In particular, Plummer's conjecture already implies Tutte's celebrated theorem that every $4$-connected planar graph is Hamiltonian (i.e. contains a Hamiltonian circuit).
For my question below to make sense, it also helps to be familiar with the definition of $H$-component where $H$ is a subgraph of $G$. Here is the definition, taken from Thomassen's paper:
Finally, an outer cycle just means the cycle bounding the outside (infinite) face of a planar graph in its plane drawing. With all the definitions out of the way, Thomassen's main theorem is the following:
Thomassen claims that the theorem above immediately implies
Plummer's conjecture: Every $4$-connected planar graph is Hamiltonian-connected.
My question is: Can somebody explain how to see this implication? I presume that we need to remove two points $x$ and $y$, which would result in a $2$-connected graph. After that, do we apply the Theorem above? But it is not clear to me what the vertex $u$ or the edge $e$ should be. I would very much appreciate if someone could elaborate and explain the details. Thanks!
graph-theory proof-explanation planar-graph hamiltonian-path
$endgroup$
add a comment |
$begingroup$
I started reading Thomassen's paper A Theorem on Paths in Planar Graphs, where he proves one of Plummer's conjectures: Every $4$-connected planar graph is Hamiltonian-connected.
Context. Recall that a graph $G$ is called Hamiltonian-connected if for every two vertices $x$ and $y$ in $G$, we can find a Hamiltonian path starting from $x$ and ending at $y$. This is a rather strong condition, and in particular implies that $G$ must have a Hamiltonian circuit (indeed, we can take two adjacent vertices $x$ and $y$, find a Hamiltonian path from $y$ to $x$, and then add the edge $xy$ back to get a Hamiltonian circuit). In particular, Plummer's conjecture already implies Tutte's celebrated theorem that every $4$-connected planar graph is Hamiltonian (i.e. contains a Hamiltonian circuit).
For my question below to make sense, it also helps to be familiar with the definition of $H$-component where $H$ is a subgraph of $G$. Here is the definition, taken from Thomassen's paper:
Finally, an outer cycle just means the cycle bounding the outside (infinite) face of a planar graph in its plane drawing. With all the definitions out of the way, Thomassen's main theorem is the following:
Thomassen claims that the theorem above immediately implies
Plummer's conjecture: Every $4$-connected planar graph is Hamiltonian-connected.
My question is: Can somebody explain how to see this implication? I presume that we need to remove two points $x$ and $y$, which would result in a $2$-connected graph. After that, do we apply the Theorem above? But it is not clear to me what the vertex $u$ or the edge $e$ should be. I would very much appreciate if someone could elaborate and explain the details. Thanks!
graph-theory proof-explanation planar-graph hamiltonian-path
$endgroup$
I started reading Thomassen's paper A Theorem on Paths in Planar Graphs, where he proves one of Plummer's conjectures: Every $4$-connected planar graph is Hamiltonian-connected.
Context. Recall that a graph $G$ is called Hamiltonian-connected if for every two vertices $x$ and $y$ in $G$, we can find a Hamiltonian path starting from $x$ and ending at $y$. This is a rather strong condition, and in particular implies that $G$ must have a Hamiltonian circuit (indeed, we can take two adjacent vertices $x$ and $y$, find a Hamiltonian path from $y$ to $x$, and then add the edge $xy$ back to get a Hamiltonian circuit). In particular, Plummer's conjecture already implies Tutte's celebrated theorem that every $4$-connected planar graph is Hamiltonian (i.e. contains a Hamiltonian circuit).
For my question below to make sense, it also helps to be familiar with the definition of $H$-component where $H$ is a subgraph of $G$. Here is the definition, taken from Thomassen's paper:
Finally, an outer cycle just means the cycle bounding the outside (infinite) face of a planar graph in its plane drawing. With all the definitions out of the way, Thomassen's main theorem is the following:
Thomassen claims that the theorem above immediately implies
Plummer's conjecture: Every $4$-connected planar graph is Hamiltonian-connected.
My question is: Can somebody explain how to see this implication? I presume that we need to remove two points $x$ and $y$, which would result in a $2$-connected graph. After that, do we apply the Theorem above? But it is not clear to me what the vertex $u$ or the edge $e$ should be. I would very much appreciate if someone could elaborate and explain the details. Thanks!
graph-theory proof-explanation planar-graph hamiltonian-path
graph-theory proof-explanation planar-graph hamiltonian-path
edited Dec 30 '18 at 7:54
Alex Ravsky
41.7k32383
41.7k32383
asked Dec 24 '18 at 20:04
PrismPrism
5,04731981
5,04731981
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Suppose $G$ is planar $4$-connected, and let $u,v$ be any two vertices of $G$. We choose a face $C$ containing $v$ and an edge $e$ of $C$, then apply the theorem to find a $v,u$-path $P$ containing $e$.
We'd like to make sure that $P$ contains at least $4$ vertices. To accomplish this, we choose $C$ and $e$ carefully: we want to make sure that neither $u$ nor $v$ is an endpoint of $C$.
Let $x,y$ be two neighbors of $v$. Since $G$ is $4$-connected, there is an $x,y$-path in $G-{u,v}$, which forms a cycle $D$ together with the edges $vx$ and $yv$. In a planar embedding of $G$, $D$ divides the plane in two regions, one of which does not contain $u$. Let $C$ be a face containing $v$ which is inside the region not containing $u$. Then $C$ has at least two vertices other than $v$, and so we can choose an edge in $C$ whose endpoints are distinct from $u$ and $v$.
(Maybe there was a more elegant way to do this step.)
Now $P$ contains at least $4$ vertices: $u$, $v$, and the endpoints of $e$. I claim that $P$ must be a Hamiltonian path.
If not - if there is a vertex $z$ not in $P$ - let $F$ be the $P$-component containing $z$. Deleting the vertices of attachment of $F$ disconnects $z$ from the remaining vertices of $P$ (there are at most $3$ vertices of attachment, but at least $4$ vertices in $P$). This means that $G$ is at most $3$-connected, violating the hypothesis.
$endgroup$
$begingroup$
Hi Misha, thank you very much for the answer. I have been traveling, so I have not been able to read your response (my apologies!) but I will do so soon, and of course give +1 when I understand the answer.
$endgroup$
– Prism
Feb 18 at 5:45
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
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%2f3051588%2fall-4-connected-planar-graphs-are-hamiltonian-connected%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$
Suppose $G$ is planar $4$-connected, and let $u,v$ be any two vertices of $G$. We choose a face $C$ containing $v$ and an edge $e$ of $C$, then apply the theorem to find a $v,u$-path $P$ containing $e$.
We'd like to make sure that $P$ contains at least $4$ vertices. To accomplish this, we choose $C$ and $e$ carefully: we want to make sure that neither $u$ nor $v$ is an endpoint of $C$.
Let $x,y$ be two neighbors of $v$. Since $G$ is $4$-connected, there is an $x,y$-path in $G-{u,v}$, which forms a cycle $D$ together with the edges $vx$ and $yv$. In a planar embedding of $G$, $D$ divides the plane in two regions, one of which does not contain $u$. Let $C$ be a face containing $v$ which is inside the region not containing $u$. Then $C$ has at least two vertices other than $v$, and so we can choose an edge in $C$ whose endpoints are distinct from $u$ and $v$.
(Maybe there was a more elegant way to do this step.)
Now $P$ contains at least $4$ vertices: $u$, $v$, and the endpoints of $e$. I claim that $P$ must be a Hamiltonian path.
If not - if there is a vertex $z$ not in $P$ - let $F$ be the $P$-component containing $z$. Deleting the vertices of attachment of $F$ disconnects $z$ from the remaining vertices of $P$ (there are at most $3$ vertices of attachment, but at least $4$ vertices in $P$). This means that $G$ is at most $3$-connected, violating the hypothesis.
$endgroup$
$begingroup$
Hi Misha, thank you very much for the answer. I have been traveling, so I have not been able to read your response (my apologies!) but I will do so soon, and of course give +1 when I understand the answer.
$endgroup$
– Prism
Feb 18 at 5:45
add a comment |
$begingroup$
Suppose $G$ is planar $4$-connected, and let $u,v$ be any two vertices of $G$. We choose a face $C$ containing $v$ and an edge $e$ of $C$, then apply the theorem to find a $v,u$-path $P$ containing $e$.
We'd like to make sure that $P$ contains at least $4$ vertices. To accomplish this, we choose $C$ and $e$ carefully: we want to make sure that neither $u$ nor $v$ is an endpoint of $C$.
Let $x,y$ be two neighbors of $v$. Since $G$ is $4$-connected, there is an $x,y$-path in $G-{u,v}$, which forms a cycle $D$ together with the edges $vx$ and $yv$. In a planar embedding of $G$, $D$ divides the plane in two regions, one of which does not contain $u$. Let $C$ be a face containing $v$ which is inside the region not containing $u$. Then $C$ has at least two vertices other than $v$, and so we can choose an edge in $C$ whose endpoints are distinct from $u$ and $v$.
(Maybe there was a more elegant way to do this step.)
Now $P$ contains at least $4$ vertices: $u$, $v$, and the endpoints of $e$. I claim that $P$ must be a Hamiltonian path.
If not - if there is a vertex $z$ not in $P$ - let $F$ be the $P$-component containing $z$. Deleting the vertices of attachment of $F$ disconnects $z$ from the remaining vertices of $P$ (there are at most $3$ vertices of attachment, but at least $4$ vertices in $P$). This means that $G$ is at most $3$-connected, violating the hypothesis.
$endgroup$
$begingroup$
Hi Misha, thank you very much for the answer. I have been traveling, so I have not been able to read your response (my apologies!) but I will do so soon, and of course give +1 when I understand the answer.
$endgroup$
– Prism
Feb 18 at 5:45
add a comment |
$begingroup$
Suppose $G$ is planar $4$-connected, and let $u,v$ be any two vertices of $G$. We choose a face $C$ containing $v$ and an edge $e$ of $C$, then apply the theorem to find a $v,u$-path $P$ containing $e$.
We'd like to make sure that $P$ contains at least $4$ vertices. To accomplish this, we choose $C$ and $e$ carefully: we want to make sure that neither $u$ nor $v$ is an endpoint of $C$.
Let $x,y$ be two neighbors of $v$. Since $G$ is $4$-connected, there is an $x,y$-path in $G-{u,v}$, which forms a cycle $D$ together with the edges $vx$ and $yv$. In a planar embedding of $G$, $D$ divides the plane in two regions, one of which does not contain $u$. Let $C$ be a face containing $v$ which is inside the region not containing $u$. Then $C$ has at least two vertices other than $v$, and so we can choose an edge in $C$ whose endpoints are distinct from $u$ and $v$.
(Maybe there was a more elegant way to do this step.)
Now $P$ contains at least $4$ vertices: $u$, $v$, and the endpoints of $e$. I claim that $P$ must be a Hamiltonian path.
If not - if there is a vertex $z$ not in $P$ - let $F$ be the $P$-component containing $z$. Deleting the vertices of attachment of $F$ disconnects $z$ from the remaining vertices of $P$ (there are at most $3$ vertices of attachment, but at least $4$ vertices in $P$). This means that $G$ is at most $3$-connected, violating the hypothesis.
$endgroup$
Suppose $G$ is planar $4$-connected, and let $u,v$ be any two vertices of $G$. We choose a face $C$ containing $v$ and an edge $e$ of $C$, then apply the theorem to find a $v,u$-path $P$ containing $e$.
We'd like to make sure that $P$ contains at least $4$ vertices. To accomplish this, we choose $C$ and $e$ carefully: we want to make sure that neither $u$ nor $v$ is an endpoint of $C$.
Let $x,y$ be two neighbors of $v$. Since $G$ is $4$-connected, there is an $x,y$-path in $G-{u,v}$, which forms a cycle $D$ together with the edges $vx$ and $yv$. In a planar embedding of $G$, $D$ divides the plane in two regions, one of which does not contain $u$. Let $C$ be a face containing $v$ which is inside the region not containing $u$. Then $C$ has at least two vertices other than $v$, and so we can choose an edge in $C$ whose endpoints are distinct from $u$ and $v$.
(Maybe there was a more elegant way to do this step.)
Now $P$ contains at least $4$ vertices: $u$, $v$, and the endpoints of $e$. I claim that $P$ must be a Hamiltonian path.
If not - if there is a vertex $z$ not in $P$ - let $F$ be the $P$-component containing $z$. Deleting the vertices of attachment of $F$ disconnects $z$ from the remaining vertices of $P$ (there are at most $3$ vertices of attachment, but at least $4$ vertices in $P$). This means that $G$ is at most $3$-connected, violating the hypothesis.
edited Feb 17 at 0:14
answered Feb 16 at 23:41
Misha LavrovMisha Lavrov
46.8k657107
46.8k657107
$begingroup$
Hi Misha, thank you very much for the answer. I have been traveling, so I have not been able to read your response (my apologies!) but I will do so soon, and of course give +1 when I understand the answer.
$endgroup$
– Prism
Feb 18 at 5:45
add a comment |
$begingroup$
Hi Misha, thank you very much for the answer. I have been traveling, so I have not been able to read your response (my apologies!) but I will do so soon, and of course give +1 when I understand the answer.
$endgroup$
– Prism
Feb 18 at 5:45
$begingroup$
Hi Misha, thank you very much for the answer. I have been traveling, so I have not been able to read your response (my apologies!) but I will do so soon, and of course give +1 when I understand the answer.
$endgroup$
– Prism
Feb 18 at 5:45
$begingroup$
Hi Misha, thank you very much for the answer. I have been traveling, so I have not been able to read your response (my apologies!) but I will do so soon, and of course give +1 when I understand the answer.
$endgroup$
– Prism
Feb 18 at 5:45
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%2f3051588%2fall-4-connected-planar-graphs-are-hamiltonian-connected%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