Euler Trails and Hamilton Cycles

Suppose the only graph edges are KL, LM, MN and NK. There is also an isolated vertex H. The route K-L-M-N-K covers every edge once and closes. It is an Euler circuit. H does not obstruct it because H has no incident edges to cover.

For a finite undirected graph with at least one edge, an Euler circuit exists exactly when every degree is even and all vertices incident with edges lie in one connected component. A loop contributes two to its vertex's degree.

The route proves the necessity of even degrees. Every arrival has a matching departure. At the starting vertex, the first departure matches the final arrival. Because every edge is used once, all incident edge ends belong to pairs.

Existence needs a separate argument. Starting at a vertex with an edge, keep taking unused edges until none is available. You cannot stop at a different vertex: an arrival there would leave an unused departure because its degree is even. The trail therefore closes at its start.

Remove the used edges. All remaining degrees are even. If unused edges remain, connectedness gives a vertex on the current route with an unused incident edge. Build a closed trail from that vertex using only unused edges, then insert it into the route. Each insertion covers more edges. Finiteness makes the process end with an Euler circuit.

In this topic, an Euler trail uses every graph edge exactly once and may be closed. An open Euler trail has different starting and ending vertices.

Assume the graph is finite and undirected, has at least one edge, and has all its edge-containing vertices in one component. Zero odd-degree vertices gives an Euler circuit. Exactly two gives an open Euler trail. More than two prevents an Euler trail.

At each intermediate visit, an arriving edge pairs with a departing edge. At the start of an open trail, one departure has no matching arrival. At its end, one arrival has no matching departure. The two endpoints are therefore the only odd-degree vertices.

To prove that the conditions suffice, add one temporary edge between the two odd vertices. This is allowed even when an edge already joins them: the proof can use an undirected multigraph with parallel edges. The two odd degrees become even, and every other degree stays even.

The augmented graph has an Euler circuit. Choose its written starting point so that the temporary edge comes last. Delete that edge. The remaining route uses each original edge once, starts at one original odd vertex and ends at the other.

Connectivity is still required. Two separate components that both contain edges cannot be covered by one walk, regardless of their odd-degree counts.

Take a simple undirected graph with n >= 3 vertices. A Hamilton cycle visits every vertex once before returning to its start. It can leave other graph edges unused.

Dirac's theorem gives one guarantee: if every vertex has degree at least n/2, the graph has a Hamilton cycle. Ore's theorem gives another: for every pair of distinct nonadjacent vertices u and v, require deg(u) + deg(v) >= n. Meeting that condition also guarantees a Hamilton cycle.

These are sufficient conditions, not necessary ones. Consider the cycle graph on nine vertices. Its ring is already a Hamilton cycle. Every degree is 2, below Dirac's bound 9/2. Nonadjacent vertices have degree sum 4, below Ore's bound 9. The graph fails both conditions and still has the cycle.

There are useful necessary conditions too. Every vertex on a Hamilton cycle needs two distinct incident edges. A degree-0 or degree-1 vertex rules out a Hamilton cycle. Failing this necessary condition proves impossibility; failing a sufficient condition does not.

Euler and Hamilton coverage do not imply one another. The complete graph on four vertices has Hamilton cycles but four odd degrees, so it has no Euler trail. Two triangles sharing just one vertex have an Euler circuit. They have no Hamilton cycle: reaching both triangles and returning would require repeating the shared vertex.

A proposed route gives you a particular object to check. For a Hamilton path, check that it lists every graph vertex exactly once and that each consecutive pair is joined by an edge. For a Hamilton cycle in a simple undirected graph, require at least three vertices. List every graph vertex once, then append the first vertex to close the route. Check every consecutive undirected edge, including the closing edge, is present and none repeats. These checks take polynomial time.

Rejecting one proposed route does not prove that every possible route fails. Deciding existence asks whether any valid route is available.

Euler trail existence has a direct decision test. With adjacency lists, check connectivity among vertices incident with edges and count odd degrees. This takes O(V + E) time, where V counts vertices and E counts edges. Under that connectivity condition, zero odd degrees gives a circuit and exactly two gives an open trail. A larger odd count rules out an Euler trail. Isolated vertices have no edges to cover.

For general simple undirected graphs, Hamilton path existence and Hamilton cycle existence are NP-complete decision problems. No polynomial-time algorithms for these general problems are known. Whether P = NP remains open, so a polynomial-time algorithm has not been proved impossible.

There are exact algorithms. One can enumerate vertex orders and check each order's required edges. That search can grow factorially with the vertex count. Special graph families and sufficient degree conditions allow some instances to be settled quickly without settling every general instance.