Graphs which can connect every pair of vertices via a hamilton path

Question

Let G be a simple undirected Graph with the following property : For every pair of vertices $(u,v)$, there is a hamilton path from $u$ to $v$. It is clear that all complete graphs have this property and that the graph must have a hamilton circle to have this property.

A hamilton path is a path visiting EVERY vertex exactly once. A hamilton circle is a circle containing EVERY vertex.

• Is there a name for such graphs ?

• Which graphs beside the complete ones have this property (Is there a nice criterion) ?

• What is the least possible number of edges for a graph with $n$ vertices to have this property ?

Answer 1

None of the answers so far address the minimum number of edges required for an $n$-vertex graph with this property.

It is easy to see that (provided $n>3$) that there can be no vertex of degree $2$. If there is, say $u$ has neighbours $v,w$, then the only path from $v$ to $w$ which uses $u$ is the path $vuw$, which is not Hamilton.

So we have all degrees at least $3$, and so the minimum number is at least $3n/2$.

In face for any even $n=6,10,14,\ldots$ there is a suitable graph with this many vertices. Suppose $n=2k$, with $k$ odd. We claim that the prism (two $k$-cycles, with edges between corresponding vertices) is such a graph. Given any start and end vertices which are not corresponding vertices on the two cycles (that case is easy), we start from one and move round the cycles towards the other, alternating between cycles, until we are about to hit the end vertex. Instead, we now stick to one cycle, go past it until we get almost back to the starting point, flip to the other cycle and then come back. This is illustrated for a particular pair on the left, going anticlockwise round the cycles. However, this may not work due to parity constraints: if this alternating movement would hit the end vertex from the wrong direction, we can't just stop and go past it. If this happens, we can just go round the cycle in the other direction (right example) and $k$ being odd will ensure that this works.

Answer 2

"Which graphs beside the complete ones have this property? (Is there a nice criterion?)"

About the criterion: I can think of every graph that fulfills Pós' theorem, Ore's theorem or Dirac's theorem conditions (because Ore's theorem implies Pós' theorem and Dirac's theorem is conclusion from Ore's theorem).

I will just prove that for Pós theorem (because I can't find it on the Internet so I think it might be hard to find it for you too):

Let $ D_n(G)= \left \{ v\in V: deg_G(v)\leq n \right \}$

Pós' theorem states that: $G$ is a graph with $p$ vertices. If for every $1\leq n < \frac {p-1}{2}$, $D_n(G)<n$ (and for $n=\frac{p-1}{2}$, $D_n(G)\leq n$ if $p$ is odd number) then $G$ is Hamiltonian.

It is easy to prove then that every two vertices in $G$ are ends of a Hamiltonian path (I won't prove the whole theorem here).

Proof: If the theorem is false then there exists counterexamples. Let $H$ be the maximal counterexample to the theorem (that means that adding any new edge to $H$ makes it Hamiltonian). Because adding edges doesn't change Pós condition and makes H Hamiltonian, we proved that every two vertices in H must be ends of some Hamiltonian path. $\square$

Answer 3

Few years over date, but given that the answer by Mateusz seems wrong: these graphs are named Hamiltonian-connected graphs and some sufficient conditions can be found in section 3.2 of this dissertation. The variants on Dirac's, Ore's, and Posa's theorems are a bit stricter.

Update: For example the equivalent of Dirac's theorem is: If G is a graph of size $n\geq3$ such that $\sigma \geq \frac{n+1}{2}$, then $G$ is Hamiltonian connected. (Where $\sigma \geq \frac{n}{2}$ is enough for Hamiltonicity).