Walks, trails, paths, circuits and cycles Problem set A Worked solutions

Graph G is shown. List all the paths of length 3 from A to C.

• A path of length 3 uses 3 edges and 4 different vertices
• Start at A, take each neighbour in turn, and keep only the routes that reach C on the last edge without repeating a vertex
• A–D–B–C; A–D–E–C

Graph G is shown. List all the cycles of length 4 that start and end at A. Write a cycle and its reverse as two separate cycles.

• A cycle of length 4 uses 4 different vertices, then returns to A
• Start at A and extend by one new vertex at a time. The last vertex must be adjacent to A
• A–C–E–F–A; A–F–E–C–A

Graph G is shown. Classify each walk as a walk, trail, path, circuit or cycle. Give the most specific name.

1. (a) E–D–A–B–F–A–E

   • Length 6. Starts and ends at E; no edge is repeated; a vertex is repeated
   • It is a circuit

2. (b) D–A–F–E

   • Length 3. Does not return to its start; no edge is repeated; no vertex is repeated
   • It is a path

3. (c) B–A–E–A–F–E–D–E

   • Length 7. Does not return to its start; an edge is repeated; a vertex is repeated
   • It is a walk

4. (d) F–E–D–A–B–F

   • Length 5. Starts and ends at F; no edge is repeated; no vertex is repeated (apart from the start and end)
   • It is a cycle

Graph G is shown.

1. (a) Write down the vertices of odd degree.

   • Degrees: A 3, B 1, C 2, D 2, E 4, F 2
   • Odd: A and B

2. (b) Find a trail that uses every edge exactly once.

   • A trail that uses every edge once must start at one odd vertex and end at the other. Start at A
   • A–E–C–D–E–F–A–B
   • It uses all 7 edges once: its length is 7

The graph shows the bus routes between six stops. An edge means that two stops are joined by a direct bus.

1. (a) List all the paths of length 3 from A to F.

   • Each path uses 3 edges and 4 different stops
   • A–B–C–F; A–E–B–F

2. (b) List all the cycles of length 4 that start and end at A. Count a cycle and its reverse separately.

   • Each cycle uses 4 different stops and returns to A
   • A–B–E–D–A; A–D–E–B–A

The graph shows the paths in a park. A warden wants to walk along every path exactly once, and finish where she started.

1. (a) Show that every vertex has even degree.

   • Degrees: A 4, B 2, C 4, D 2, E 4, F 2
   • All are even

2. (b) Find a route that starts and ends at A and uses every edge exactly once.

   • With no odd vertices a trail can start anywhere and return to its start
   • A–F–E–A–B–C–D–E–C–A
   • It uses all 9 edges once

3. (c) Is your route a cycle? Give a reason.

   • The route is closed and no edge is repeated, so it is a circuit
   • A, C and E appear more than once, so it is not a cycle

A delivery driver drives between six depots. Each edge is a road. Here are three routes. Route 1: A–B–C–D–E–F–C–E. Route 2: D–E–F–C–B–A–D. Route 3: B–C–B–C–F–E.

1. (a) Which routes use no road twice?

   • Route 1: does not return to its start; no edge is repeated; a vertex is repeated
   • Route 2: starts and ends at D; no edge is repeated; no vertex is repeated (apart from the start and end)
   • Route 3: does not return to its start; an edge is repeated; a vertex is repeated

2. (b) Which routes are cycles?

   • A cycle is a closed route with no repeated vertex: Route 2

The diagram shows the complete graph K5.

1. (a) How many paths of length 3 are there from A to B?

   • A path A–x–y–B: x and y are two different vertices from the other 3
   • 3 × 2 = 6

2. (b) How many cycles of length 3 start and end at A? Count a cycle and its reverse separately.

   • A cycle A–x–y–A: x and y are two different vertices from the other 4
   • 4 × 3 = 12

Graph G is shown.

1. (a) Find a trail from A to F that uses every edge exactly once.

   • Degrees: A 3, B 4, C 2, D 2, E 4, F 3
   • Only A and F are odd, so the trail starts at A and ends at F
   • A–E–D–A–B–F–C–B–E–F

2. (b) A new edge AF is added. Find a circuit that uses every edge, including the new one, exactly once, starting at A.

   • Add the edge F–A at the end of the trail: A–E–D–A–B–F–C–B–E–F–A
   • Every degree is now even, and the route returns to A
   • A–E–D–A–B–F–C–B–E–F–A