Minimum degree requirements for a graph to be Hamilton-connected, like Dirac’s classic theorem for Hamilton cycles.

graph theoryhamiltonian-path

A classic theorem of Dirac says that every graph with at least 3 vertices and minimum degree at least $\frac{n}{2}$ has a Hamilton cycle.

Is there a similar characterization for Hamilton-connected graphs? Ie, something of the form
"Every graph with minimum degree at least $X$ is Hamilton-connected?"

Best Answer

Actually, there is: every graph with minimum degree at least $\frac{n+1}{2}$ is Hamilton-connected!

To see this, let $G$ be such a graph and note that $G$ is Hamilton-connected if and only if for any pair of vertices $u,v$ of $G$, the graph $G' = G + x + ux + vx$ is Hamiltonian, where $x$ is a new vertex. The key ingredient now is the Bondy-Chvátal theorem, which says that if $u',v'$ are non-adjacent vertices in a graph such that the sum of their degrees is at least the number of vertices, then adding the $u'v'$ edge to the graph doesn't change whether it has a Hamiltonian cycle. In our case, $G'$ is a graph on $n+1$ vertices and each vertex in $G'-x$ has degree at least $\frac{n+1}{2}$. This means that we can add an edge between every pair of vertices in this subgraph, so that $G'$ becomes a complete graph plus a vertex of degree two. But such a graph is clearly Hamiltonian, which is what we wanted to show.

In fact, using the same idea the Bondy-Chvátal theorem itself has the following analogue for Hamilton-connected graphs: if $G$ is a graph on $n$ vertices and $u,v$ are non-adjacent vertices with $\deg(u) + \deg(v) \geq n+1$, then $G$ is Hamilton-connected if and only if $G+uv$ is Hamilton-connected.

Related Question