Walks
A walk is a sequence of edges, each one starting where the last one ended. It is written as the list of vertices it reaches, such as A-B-C-B, and it may repeat anything, vertices and edges alike. Its length is its number of edges, so A-B-C-B has length 3, and it uses the edge between B and C twice, once in each direction.
Each of the other route words is a walk with something it may not repeat. They are shown here on the figure-eight graph: two triangles, ABC and CDE, that share the vertex C.
The walk A-B-C-B, with each vertex numbered in the order it is reached. B is reached second and fourth, and the gold edge BC is used twice.
Trails
A trail is a walk that uses no edge twice. It may pass through a vertex more than once, arriving and leaving on different edges each time.
A-B-C-D-E-C is a trail. Its five edges, AB, BC, CD, DE and EC, are all different, and it passes through C twice, as its third and its sixth vertex.
The trail A-B-C-D-E-C: five different gold edges, with C reached third and sixth.
Paths
A path is a walk that visits no vertex twice. A-B-C-D-E is a path of length 4, through all five vertices.
A path cannot repeat an edge either. Using an edge a second time means standing at one of its ends a second time, and that is a repeated vertex. So every path is a trail, but a trail need not be a path.
A walk from one vertex to another always contains a path between them. Wherever the walk comes back to a vertex it has already visited, cut out the stretch in between. The walk A-C-D-E-C-B visits C twice; cut out C-D-E-C, and the path A-C-B is left.
The path A-B-C-D-E: each of the five vertices is reached once.
Circuits
A circuit is a trail that ends where it began. A-B-C-D-E-C-A is a circuit: it starts and ends at A, uses each of the six edges once, and passes through C twice on the way.
A walk that ends where it began but repeats an edge is a closed walk, not a circuit. A-B-A goes along AB and straight back, using the same edge twice.
The circuit A-B-C-D-E-C-A: each gold edge is used once, and the route comes back to A as its seventh vertex.
Cycles
A cycle is a circuit that repeats no vertex except the one at both ends. A-B-C-A is a cycle of length 3, and so is C-D-E-C.
The circuit A-B-C-D-E-C-A is not a cycle, because it passes through C twice before it returns to A. The figure-eight has no other cycles than its two triangles: a closed route that visits both triangles must pass through C on the way out and again on the way back, since C is the only vertex they share.
The cycle A-B-C-A in gold: it closes, and no vertex but A is reached twice.
Naming a route
The words nest inside each other: every path is a trail, every trail is a walk, and every cycle is a circuit. Naming a route means giving the most precise word that fits, and three questions find it.
First, does it repeat an edge? If so, it is a walk, or a closed walk if it ends where it began. If not, it is a trail, and the second question is whether it ends where it began. A trail that does not close is a path when it repeats no vertex, and only a trail when it does. A trail that closes is a cycle when no vertex but the start repeats, and a circuit otherwise.
B-A-C-E-D-C-B closes at B and repeats no edge, so it is a circuit; it passes through C twice, so it is not a cycle. A-B-C-A-B uses AB twice, so it is a walk. A-C-B repeats nothing and does not close, so it is a path of length 2.
odd vertices = 2, so an Euler trail exists, but it must run from one odd vertex to the other
Add edges until you can trace every edge once and finish where you started
Five vertices joined in a line by 4 edges: the two ends have odd degree, so a route can use each edge once but cannot finish where it started. Add the fifth edge to close the ring, and the numbered gold route uses each edge once and returns to its start: a circuit, and a cycle too, since no vertex repeats. Each vertex shows its degree.
The usual mistakes
Calling a trail a path because no edge repeats. A-B-C-D-E-C passes through C twice, so it is a trail but not a path.
Calling a circuit a cycle because it closes. A-B-C-D-E-C-A passes through C in the middle, so it is a circuit but not a cycle.
Calling a closed walk a circuit. A-B-A ends where it began, but it uses AB twice.
Counting the vertices for the length. A-B-C-A lists four vertices but has three edges, so its length is 3.
A courier and a museum
In the first application below, a van’s log lists the junctions it reached, and each day’s route is named by looking for a repeated street, a repeated junction and a return to the depot. In the second, a guard’s patrol is a circuit that is not a cycle, and the short tours from the hall are cycles counted by the galleries next to it.
Worked example: A Courier's Delivery Logs for Two Days, and What Each Day's Route Is Called
Question A courier's van works from a depot at junction A in a town with six junctions, A, B, C, D, E and F. The town's eight streets join A and B, A and F, B and C, B and E, B and F, C and D, C and E, and D and E. The van's log lists the junctions in the order the van reached them, and between two junctions next to each other in the log it drove the street that joins them. Here a trail repeats no street, a path repeats no junction, a circuit is a trail that ends where it began, and a cycle is a circuit that repeats no junction but its start. Monday's log reads A, B, C, D, E, B, F. Tuesday's log reads A, F, B, C, E, D, C, B, A. (a) Which of the words walk, trail, path, circuit and cycle describes Monday's route most precisely, and which junction decides it? (b) The company's rule is that no street is driven twice in one shift. Did Tuesday's route keep the rule, which street decides it, and which of the five words describes the route most precisely?
1.Model the town as a graph: a vertex for each junction and an edge for each street. A trail is a walk that uses no edge twice, and a path is a walk that visits no vertex twice. A circuit is a trail that ends where it began, and a cycle is a circuit that visits no vertex twice except the one it starts and ends at.
Each junction is a vertex and each street an edge. The depot is at A. 2.List Monday's streets in order: A–B, B–C, C–D, D–E, E–B and B–F. These are 6 different streets, so no street is repeated and the route is at least a trail.
Monday's route uses 6 streets, and no street appears twice. 3.(a) Monday's route reaches B twice, once from A and again from E, so it is not a path. It starts at A and ends at F, so it is not closed either. The most precise word is trail, and junction B decides it.
(a) Monday's route reaches B twice and ends at F, so it is a trail, not a path. 4.List Tuesday's streets in order: A–F, F–B, B–C, C–E, E–D, D–C, C–B and B–A. The van drove 8 times along a street, but B–C and C–B are the same street, so it used only 7 different streets.
Tuesday's route has 8 drives along only 7 different streets. The street from B to C is drawn in red. 5.(b) Street B–C was driven twice, so the route is not a trail, and therefore not a circuit or a cycle, even though it ends at A where it began. The most precise word is walk (a closed walk), and street B–C broke the rule. Check: every other street in Tuesday's list appears exactly once.
(b) B–C is driven twice, so Tuesday's route is a closed walk, not a circuit.
Answer: (a) A trail: its 6 streets are all different, but it reaches junction B twice, so it is not a path, and it ends at F rather than A; (b) no: street B–C was driven twice, so the van used only 7 different streets in 8 drives, and the route is a closed walk, not a circuit
Common mistakes
- Calling Monday's route a path because no street is repeated. A path must also visit no junction twice, and Monday's route reaches B twice.
- Calling Tuesday's route a circuit because it starts and ends at the depot. A circuit is a trail, so it may not use any street twice, and Tuesday's route drives B–C twice.
More eulerian and hamiltonian routes problems, worked step by step →
Worked example: Doorways Between the Rooms of a Small Museum, a Guard's Evening Patrol, and the Short Tours From the Entrance Hall
Question A small museum has an entrance hall H and four galleries, A, B, C and D. Doorways join H and A, H and B, H and C, A and B, B and C, A and D, B and D, and C and D. (a) A trail repeats no doorway, a path repeats no room, a circuit is a trail that ends where it began, and a cycle is a circuit that repeats no room but its start. A guard's evening patrol goes H, A, B, D, C, B, H. Which of the words walk, trail, path, circuit and cycle describes the patrol most precisely, and which room decides it? (b) The museum wants short tours that start and end in the hall, pass through exactly three galleries, and enter no gallery twice. A tour and the same tour walked in reverse count as one. How many such tours are there?
1.Model the museum as a graph: a vertex for each room and an edge for each doorway. The patrol goes through the doorways H–A, A–B, B–D, D–C, C–B and B–H, which are 6 different doorways.
Each room is a vertex and each doorway an edge. The patrol uses 6 different doorways. 2.(a) No doorway is used twice and the patrol ends in H, where it began, so it is a circuit. It passes through gallery B twice, so it is not a cycle. The most precise word is circuit, and room B decides it.
(a) The patrol returns to H and repeats no doorway, but it passes through B twice: a circuit, not a cycle. 3.A short tour is a cycle of length 4 through H: the hall, a gallery x, a gallery y, a gallery z, and back to the hall. So x and z must both have a doorway to H, which means they are two of A, B and C, and y must have a doorway to each of them.
A short tour is a cycle of length 4 through H. The galleries next to the hall are two of A, B and C. 4.Take each pair of galleries next to the hall in turn. A and B both open into D, which gives H–A–D–B–H. A and C both open into B and into D, which gives H–A–B–C–H and H–A–D–C–H. B and C both open into D, which gives H–B–D–C–H.
Each pair of galleries next to the hall, with a gallery joined to both. The tour H–A–D–C–H is drawn. 5.(b) There are 4 tours. Each pair was taken once, so a tour and its reverse, which has the same two galleries next to the hall, are counted once. Check: D has no doorway to the hall, so it can only be the middle gallery, and it is the middle gallery in three of the four tours.
(b) 4 tours, a tour and its reverse counted once.
Answer: (a) A circuit: its 6 doorways are all different and it returns to H, but it passes through room B twice, so it is not a cycle; (b) 4 tours: H–A–D–B–H, H–A–B–C–H, H–A–D–C–H and H–B–D–C–H
Common mistakes
- Calling the patrol a cycle because it returns to the hall and uses no doorway twice. A cycle also visits no room twice except its start, and the patrol passes through B twice.
- Counting H–A–D–B–H and H–B–D–A–H as two tours. They are the same tour walked in reverse, which the question counts once; listing the tours by the pair of galleries next to the hall avoids the double count.
More eulerian and hamiltonian routes problems, worked step by step →