8
$\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:

enter image description here

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:

enter image description here

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!

$\endgroup$
0
$\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.