Discrete Math › Section C · Graph theory › Topic C.5
Euler trails and Hamilton paths
A snowplough wants to clear every street once; a delivery van wants to call at every address once. The first question, about edges, has a complete and simple answer. The second, about vertices, is one of the hardest problems in computing.
Seven bridges
The city of Königsberg (now Kaliningrad) stood on both banks of a river with two islands, and seven bridges linked its four land areas. Residents wondered whether a stroll could cross every bridge exactly once. Leonhard Euler showed, in work usually dated to 1736, that it cannot. He treated each land area as a vertex and each bridge as an edge, giving a multigraph with degrees 5, 3, 3 and 3. That move, throwing away everything except what is connected to what, is often called the beginning of graph theory.
Euler trails and circuits
An Euler trail is a walk that uses every edge of a graph exactly once. An Euler circuit is an Euler trail that finishes where it started. Vertices may be visited many times; it is the edges that must each be used once. Multigraphs are allowed, since bridges and streets often run in parallel. Think of tracing a figure without lifting your pen and without going over any line twice: you are looking for an Euler trail of the figure's graph.
Why degrees decide it
Follow an Euler trail and watch any vertex in the middle of the walk. Every visit arrives along one edge and leaves along another, using up two of its edges. So every vertex other than the start and finish must have even degree. For a circuit the start and finish are the same vertex, and its first exit pairs with its final arrival, so it is even too. A graph with more than two odd-degree vertices therefore has no Euler trail. Königsberg had four, so the stroll was impossible.
Euler's theorem
The converse also holds, which makes the test complete. Let \(G\) be a connected graph or multigraph. 1. \(G\) has an Euler circuit if and only if every vertex has even degree. 2. \(G\) has an Euler trail that is not a circuit if and only if exactly two vertices have odd degree, and then every such trail starts at one of them and ends at the other. Since the number of odd-degree vertices is always even, these are the only cases: zero odd vertices gives a circuit, two gives a trail, four or more gives neither.
Worked example: tracing a trail
A graph has edges ab, ac, bc, bd, cd, ce, de and df. 1. Degrees: a 2, b 3, c 4, d 4, e 2, f 1. 2. It is connected, and exactly two vertices, b and f, are odd, so an Euler trail exists from b to f, but no circuit. 3. Build it, avoiding any edge whose removal would cut off edges you have not yet used: b, a, c, b, d, c, e, d, f. 4. Check: the walk uses 8 edges, namely ba, ac, cb, bd, dc, ce, ed and df, each once, and the graph has exactly 8 edges.
Worked example: fixing Königsberg
The four land areas have degrees 5, 3, 3 and 3: all odd. 1. Each new bridge raises the degree of both its ends by 1. 2. One bridge between two of the odd areas leaves exactly two odd vertices, so an Euler trail becomes possible, starting and ending at the two still-odd areas. 3. For a circuit, all four must become even. One bridge fixes at most two of them, so at least two bridges are needed, and two do it: pair the four areas up and bridge each pair. Snowploughs and street sweepers solve the same problem by repeating as few streets as possible, the route inspection or Chinese postman problem.
Hamilton paths and cycles
A Hamilton path visits every vertex of a graph exactly once. A Hamilton cycle does the same and then returns along an edge to its start. Edges may go unused. The question sounds like the Euler one, but no simple test is known. Deciding whether a graph has a Hamilton cycle is NP-complete: no efficient method is known for large graphs, and finding one would settle a famous open problem in computer science. In practice we use sufficient conditions, which guarantee a cycle, and simple obstructions, which rule one out.
A guarantee: Dirac's theorem
Dirac's theorem says that a simple graph with \(n \ge 3\) vertices, in which every vertex has degree at least \(n/2\), has a Hamilton cycle. With many edges at every vertex, a cycle cannot avoid anyone. For example, every vertex of \(K_{4,4}\) has degree 4, which is half of 8, so it has a Hamilton cycle. The condition is sufficient but not necessary: the cycle \(C_{10}\) is itself a Hamilton cycle, though each of its vertices has degree only 2, far below 5.
Worked example: proving there is no Hamilton cycle
Take \(K_{2,3}\), with sides {x, y} and {1, 2, 3}. 1. Every edge joins the two sides, so any walk alternates sides. 2. A Hamilton cycle would alternate all the way round and return to its start, so it would use equally many vertices from each side. 3. The sides have 2 and 3 vertices, so no Hamilton cycle exists. 4. A Hamilton path is still possible, because a path can begin and end on the larger side: 1, x, 2, y, 3. The same argument shows that a bipartite graph with unequal sides never has a Hamilton cycle. Another quick obstruction: a vertex of degree 1 rules out any Hamilton cycle.
The travelling salesperson problem
Give every edge a cost and ask for the cheapest Hamilton cycle: this is the travelling salesperson problem. It models delivery rounds, drilling holes in circuit boards and scheduling a telescope's observations. Because the Hamilton cycle question itself is hard, exact solutions become impractical as the number of stops grows; even 20 cities give about \(6 \times 10^{16}\) different round trips. Practical software uses heuristics, methods that quickly find very good routes without a guarantee of the best one.
Common mistakes to avoid
First, mixing up the two ideas: Euler means every edge once, Hamilton means every vertex once. Second, forgetting that Euler's theorem needs the graph to be connected; two separate triangles have all degrees even but no Euler circuit. Third, starting an Euler trail at an even vertex when two vertices are odd; it must start at one odd vertex and end at the other. Fourth, reading Dirac's theorem backwards: a graph with small degrees can still have a Hamilton cycle.
Key takeaways
An Euler trail uses every edge once; an Euler circuit also returns to its start. A connected graph has an Euler circuit exactly when all degrees are even, and an Euler trail that is not a circuit exactly when two vertices are odd, which must be its ends. A Hamilton path visits every vertex once, and deciding whether a Hamilton cycle exists is NP-complete. Dirac's theorem gives a sufficient condition, degrees of at least \(n/2\); parity arguments and degree-1 vertices show when no cycle exists.
Flashcards
Flashcard
Seven bridges, four land areas, no walk crossing each once
Test your understanding
Question 1 of 5
A connected graph has vertex degrees 2, 5, 4, 3, 2 and 4. What can you say?
Question 2 of 5
In the Königsberg graph, the four land areas have degrees 5, 3, 3 and 3. What is the smallest number of new bridges that would allow a walk crossing every bridge exactly once and returning to its start?
Question 3 of 5
A simple graph has 10 vertices, and every vertex has degree at least 5. What does Dirac's theorem tell you?
Question 4 of 5
A street sweeper must drive along every street of a district exactly once and return to the depot. Which idea models this task?
Question 5 of 5
Which statement about the complete bipartite graph K₂,₃ is true?
