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!
Best Answer
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.