Hamiltonian circuit and graphs

An Hamiltonian path on a graph is a path going through every vertex of the graph once and only once.
An Hamiltonien circuit or tour is a circuit (closed path) going through every vertex of the graph once and only once.
A graph is said to be Hamiltonian if there is an Hamiltonian circuit on it.

This name comes from a game imagined by Sir W. Hamilton in 1859 : A traveller wants to visit 20 towns on the vertices of a dodecahedron, going once at every town and returning to the starting point.
The dodecahedron could be "flatened" on the following graph.
There are a lot of solutions, but they all reduce to only one by symetries : The Hamiltonian circuit cuts the dodecahedron in two identical parts build of 6 connected pentagons One of them build the "inner" part of the Hamiltonian circuit, the other is the "outer" part on the planar drawing of the dodecahedron.
They can be glued end to end to build an Hamiltonian circuit on the dual graph (icosahedron).

Not every graph is Hamiltonian : An Hamiltonian graph must be 2-connected, that is we have to delete at least 2 vertices to split the graph in two disconnected parts.
This is not enough, as shown by this smallest 2-connected non Hamiltonian graph :

Note also that we take care only of simple graphs (without loops and no more than one arc between two vertices). The loops can be deleted as coming back to the vertex we have just visited. The double arcs also are useless and can be deleted. We'll assume in the sequel that all graphs are simple and connected graphs.

There are other necessary conditions for a graph to be Hamiltonian.
There are also some sufficient conditions. We don't know any general necessary and sufficient condition.

Necessary conditions

In addition to 2-connectiveness of the graph, mention the Grinberg theorem and the dissection theorem.

Grinberg theorem

Given a simple planar Hamiltonian graph. The Hamiltonien circuit divides the plane in two areas : the inside and the outside of the circuit.
Let's consider first the inside. The diagonal inner arcs (those which are not on the circuit) are entirely inside (planar graph) and define inner areas (faces). If d is the number of inner arcs, there are d+1 inner areas. Let Fk the number of inner areas with k arcs.
This gives ∑ Fk = d + 1.
Also each of the Fk areas has k arcs, hence the total number of arcs on these areas is
∑ k Fk = N + 2d with N the number of arcs on the Hamiltonian circuit, and 2d because the diagonal arcs are counted twice.
Hence eliminating d : ∑ (k - 2)Fk = N - 2.
Consider now the outside of the circuit, including the infinite area outside the graph. Let Gk the number of outer areas with k arcs, we deduce in the same way that :
∑ (k - 2)Gk = N - 2 and finally the Grinberg relation :

 ∑ (k - 2)(Fk - Gk) = 0  

Dissection theorem

We name "dissection" of a graph a set of not connected elementary paths and circuits (without common vertices) covering completely the graph (every vertex is in one of these paths or circuits).
We name "value" of the dissection, the number of open paths.
Of course this means a necessary condition for a graph to have an Hamiltonian path is that the minimum value of all dissections is at most 1. And for a graph to have an Hamiltonian circuit, the minimum value is 0.

Remains to find a dissection with minimal value of a graph G.
There is a systematic method to find this dissection. Build at first a bipartite graph H of rank 2N from the graph G, N being the rank of graph G. We search then a maximum coupling on H and we deduce a minimum value dissection of graph G. We'll not say more about this method (see Berge - Graphs and Hypergraphs). The algorithm is too complicated to be used by hand.

Sufficient conditions

Apart specific cases, we know also several sufficient conditions for a graph to be Hamiltonian, considering the degree of each vertex, that is the number d(i) of arcs at each vertex .

Specific graphs

Known Hamiltonian graphs are :

Ore condition

If for any pair of vertices (i,j) of graph G not connected by an arc, d(i)+d(j)≥N, then G is Hamiltonian.

Dirac condition

If for any vertex d(i)≥N/2, then G is Hamiltonian.

Oriented graphs

For oriented graphs (arcs have a direction), there exist also some sufficient conditions for the graph to be Hamiltonian.
Name d+(i) the number of arcs leaving vertex i, d-(i) the number of arcs arriving to vertex i,
and d(i)=d+(i)+d-(i) the number of arcs with any end at vertex i.
A necessary condition for a graph to be Hamiltonian is the graph must be "strongly connected", that is any two vertices are connected by a path, with all arcs in the same direction.
As for the non oriented case, loops and doubled arcs are of no use.
We then consider only strongly connected 1-graphs without loops.

Meyniel theorem

If in a strongly connected graph without loops, every pair of vertices i and j not connected by an arc satisfies :
d(i)+d(j)≥2N-1, then this graph is Hamiltonian.

Corollaries

 

Home Arithmetic Geometric Misc Topics Scripts Games Exercices Mail Version Franšaise Previous topic Next topic