# All 4-connected planar graphs are Hamiltonian-connected

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!

## 1 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.

• 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. – Prism Feb 18 at 5:45