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

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 ?

• I don't think a Hamiltonian circuit is a necessary consequence, if we mean the same thing when we say that. Consider the graph on a,b,c where a is adjacent to b and c. Eg b-a-c. There is a Hamiltonian path from each vertex to every other vertex, but there is no Hamiltonian circuit on the graph. – Tyler Sep 2 '14 at 20:52
• Ah, okay. That makes this quite a bit more interesting. – Tyler Sep 2 '14 at 21:42
• If a graph has the given property, it is $3$-connected. – Peter Sep 3 '14 at 17:37

"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$

• There are two things that are unclear to me : 1) Is H (the maximal counterexample) non-hamiltonian ? Then pos condition cannot hold. 2) Did you consider the case, when the vertices are already neighbours ? Then the edge between these vertices cannot be add. Perhaps your definition of hamiltonian path is different from mine : A hamiltonian path must visit EVERY vertex exactly once. – Peter Sep 4 '14 at 12:20
• @Peter: H is the maximal counterexample that fulfills Pós condition and is non-hamiltonian. If the theorem is false it must exist, since we are talking about graphs with finite sets of vertices. 2) I have the same definition of Hamiltonian path and I don't quite understand your question. If two vertices are neigbors it's quite clear that you can't add a new edge between them. But it doesn't mean Hamiltonian path between them doesn't exist - just take a look at a simple cycle $C_n$. You can construct hamiltonian path between every two neigbors. – Mateusz Sep 4 '14 at 14:27