Every vertex, not every edge
An Eulerian circuit uses every edge exactly once. A Hamiltonian cycle visits every vertex exactly once and returns to where it started, and it may leave edges unused. A Hamiltonian path visits every vertex exactly once without returning.
The two questions have different answers. The figure-eight graph, two triangles sharing C, has the Eulerian circuit A-B-C-D-E-C-A, but no Hamiltonian cycle: C is the only vertex the triangles share, so a closed route through all five vertices would pass through C twice. It does have a Hamiltonian path, A-B-C-D-E, which never has to come back.
The figure-eight. A closed route through both triangles passes through C, in gold, twice, so the graph has no Hamiltonian cycle.
A Hamiltonian cycle
The graph below has five vertices and seven edges: the ring AB, BC, CD, DE and EA, and the two chords AC and BE. The ring A-B-C-D-E-A touches all five vertices once and closes, so it is a Hamiltonian cycle. It leaves the chords unused.
A Hamiltonian cycle through n vertices uses exactly n edges, one arriving at each vertex: here 5 of the 7.
The Hamiltonian cycle A-B-C-D-E-A in gold. The chords AC and BE are not used.
Finding every one
No test on the degrees decides whether a Hamiltonian cycle exists, so the way to be sure is to try the routes in an organized way, and the vertices with few edges are the place to start.
A vertex of degree 2 forces both of its edges into every Hamiltonian cycle, because the cycle must arrive and leave along two different edges. D has only CD and DE, so every Hamiltonian cycle contains C-D-E. What is left is to get from E back to C through A and B. E-A-B-C uses EA, AB and BC; E-B-A-C uses EB, BA and AC. All of those edges exist, so the graph has exactly 2 Hamiltonian cycles: A-B-C-D-E-A and A-B-E-D-C-A.
The second Hamiltonian cycle, A-B-E-D-C-A, in gold. It uses both chords and leaves BC and EA unused.
Hamiltonian paths
Drop the closing edge of a Hamiltonian cycle, and a Hamiltonian path is left. A-B-C-D-E visits every vertex once and stops at E, without using EA to return to A.
So a graph with a Hamiltonian cycle always has a Hamiltonian path. The reverse fails, as the figure-eight shows.
The Hamiltonian path A-B-C-D-E in gold: every vertex once, and no return to A.
When there is none
Remove the edges DE and EA. Now E has only one edge, BE. A cycle through E would have to arrive along one edge and leave along another, and with a single edge it would use BE twice. So no Hamiltonian cycle exists.
A Hamiltonian path can still end at E. D now has only CD, so a path has to start or end at D too, and its middle has to run from C to B through A. The only Hamiltonian path is D-C-A-B-E.
E has a single edge, in gold, so no cycle can pass through E.
Ruling a cycle out, and why that is not enough
Some checks rule a Hamiltonian cycle out. A vertex of degree 1 does, as E showed. So does a vertex whose removal splits the graph into pieces, like C in the figure-eight: the cycle would have to pass through it on the way into the far piece and again on the way back.
Passing those checks proves nothing. In the graph below, A and B are each joined to X, Y and Z. It is connected, every degree is at least 2, and removing any one vertex leaves the rest joined. Yet there is no Hamiltonian cycle. Every edge runs between the pair A, B and the three X, Y, Z, so a cycle has to alternate between the two sides and visit each side equally often, and 2 vertices cannot alternate with 3.
This is what the lack of a degree test means: degrees can rule a Hamiltonian cycle out, but only a route that works, or a search that has tried every possibility, settles the question.
A and B are each joined to X, Y and Z. Every degree is at least 2, but a cycle would have to alternate sides, and the sides hold 2 and 3 vertices.
Complete graphs
In a complete graph every pair of vertices is joined, so every order of the vertices gives a Hamiltonian cycle. With n vertices, fix the start; the other n − 1 can follow in (n − 1)! orders, and each cycle is counted twice, once in each direction. So there are (n − 1)! ÷ 2 Hamiltonian cycles.
The complete graph on 4 vertices has 3! ÷ 2 = 3, and on 5 vertices 4! ÷ 2 = 12. On 11 vertices there are already 10! ÷ 2 = 1,814,400, which is why trying every cycle soon becomes slow.
The usual mistakes
Mixing up the two names. Eulerian routes cover every edge; Hamiltonian routes visit every vertex.
Calling a closed route Hamiltonian when it misses a vertex. A-B-E-A closes, but it never reaches C or D.
Calling a Hamiltonian path a cycle because it visits every vertex. A-B-C-D-E stops at E; it is a cycle only if it returns to A.
Deciding that a cycle exists because every degree is at least 2. That is needed, but the graph with A and B joined to X, Y and Z shows it is not enough.
Counting a cycle and its reverse as two cycles.
A band’s tour and a ferry’s round trip
In the first application below, a tour that plays each city once is a Hamiltonian path, built city by city from the home city, and a round trip is a Hamiltonian cycle forced by the cities with only two lines. In the second, an island with one route rules a round trip out, and after a new route the main island still splits the others into two groups.
Worked example: A Band's Tour of Six Cities by Train, the Orders That Play Each City Once, and the Round Trips From Home
Question A band plans a tour of six cities by train: its home city H and the cities B, C, D, E and F. Direct train lines join H and C, H and E, B and D, B and E, C and D, C and E, C and F, D and F, and E and F. The band will play each city exactly once, and it travels only on direct lines. (a) The tour starts at H and ends at F, where the band has a festival slot. How many different orders of the six cities are possible? (b) The festival is canceled, and the band now wants a round trip: start at H, play the other five cities once each, and return to H. How many different round trips are there, if a trip and the same trip in reverse count as one?
1.Model the cities as a graph: a vertex for each city and an edge for each direct line. A tour that plays every city once is a Hamiltonian path, and a round trip is a Hamiltonian cycle. There is no degree test for either, so build the orders city by city.
Each city is a vertex and each direct line an edge. A tour playing every city once is a Hamiltonian path. 2.H has lines only to C and E, so the second city is C or E. From C the next city is D or E; F cannot come yet, because it must be last. C then D forces D then B, then E, then F: H–C–D–B–E–F. C then E forces E then B, then D, then F: H–C–E–B–D–F.
Second city C: two orders reach F last. The order H–C–E–B–D–F is drawn. 3.From E the next city is B or C. E then B forces B then D, and D then C, then F: H–E–B–D–C–F. E then C forces C then D and D then B, but B's lines run only to D and E, which are already played, so that branch fails.
Second city E: one order reaches F last, and one gets stuck at B. 4.(a) There are 3 orders: H–C–D–B–E–F, H–C–E–B–D–F and H–E–B–D–C–F.
(a) 3 orders from H to F. 5.For a round trip, H has only two lines, so the trip leaves along one and returns along the other. The rest of the trip is a path from C to E through B, D and F. B has only the lines to D and E, so the path must end D, B, E, and the city between C and D is F.
A round trip uses both of H's lines, and B must sit between D and E. 6.(b) There is 1 round trip: H–C–F–D–B–E–H. Check each step: H–C, C–F, F–D, D–B, B–E and E–H are all direct lines.
(b) 1 round trip: H–C–F–D–B–E–H.
Answer: (a) 3 orders: H–C–D–B–E–F, H–C–E–B–D–F and H–E–B–D–C–F; (b) 1 round trip, H–C–F–D–B–E–H
Common mistakes
- Counting orders that reach F before the last city, such as H–C–F–D–B–E. The festival is the last date, so F must end the tour.
- Counting H–C–F–D–B–E–H and H–E–B–D–F–C–H as two round trips. They are the same trip in reverse, which the question counts once.
More eulerian and hamiltonian routes problems, worked step by step →
Worked example: A Ferry Company's Plan for a Round Trip Calling at Each of Seven Islands Once, Before and After a New Route
Question A ferry company serves seven islands: the main island M, and P, Q, R, S, U and Z. Its nine routes join M and P, M and R, M and S, M and U, P and Q, P and R, Q and R, S and U, and U and Z, and every route runs both ways. The company wants a round trip that starts at M, calls at every other island exactly once, and returns to M. (a) Is such a round trip possible with these routes? Give the fact that settles it. (b) The company adds a route between Z and S. Is the round trip possible now? Give the fact that settles it.
1.Model the islands as a graph: a vertex for each island and an edge for each route. The round trip is a Hamiltonian cycle, which arrives at and leaves every island once, using two of its routes.
Each island is a vertex and each route an edge. The round trip is a Hamiltonian cycle. 2.Z has only one route, to U. A cycle through Z would have to arrive and leave along that one route, and a cycle cannot use an edge twice.
A cycle arrives at and leaves every vertex, but Z has only one edge. 3.(a) No: Z has degree 1, so no round trip can call at Z and carry on.
(a) No: Z has degree 1. 4.After the new route, Z has degree 2, and every island has at least 2 routes: M has 4, P, R, S and U have 3 each, and Q and Z have 2 each. The degrees no longer rule the trip out. Now remove M: P, Q and R are left joined only to one another, and S, U and Z only to one another.
The new route Z–S gives Z degree 2, and no island has fewer than 2 routes. 5.(b) No: M is a cut vertex. The only routes between the group P, Q, R and the group S, U, Z pass through M, so a trip that calls at both groups must pass through M between them as well as start and finish there. It would visit M twice, which a Hamiltonian cycle does not allow.
(b) No: M is a cut vertex, and removing it leaves 2 groups.
Answer: (a) No: Z has only 1 route, to U, so a trip cannot arrive at Z and leave again; (b) No: M is a cut vertex, since removing it splits the islands into 2 groups, P, Q, R and S, U, Z, so the trip would have to pass through M twice
Common mistakes
- Deciding (b) yes because every island now has at least two routes. Having two routes at each island is needed for a round trip, but it is not enough: M still carries every route between the two groups.
- Planning in (a) to call at Z last and stop there. The trip must return to M, and from Z the only route out is the one the ferry arrived on.
More eulerian and hamiltonian routes problems, worked step by step →