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

Graph G is shown. List all the paths of length 3 from A to 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.

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
2. (b) D–A–F–E
3. (c) B–A–E–A–F–E–D–E
4. (d) F–E–D–A–B–F

Graph G is shown.

1. (a) Write down the vertices of odd degree.
2. (b) Find a trail that uses every edge exactly once.

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.
2. (b) List all the cycles of length 4 that start and end at A. Count a cycle and its reverse separately.

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.
2. (b) Find a route that starts and ends at A and uses every edge exactly once.
3. (c) Is your route a cycle? Give a reason.

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?
2. (b) Which routes are cycles?

The diagram shows the complete graph K5.

1. (a) How many paths of length 3 are there from A to B?
2. (b) How many cycles of length 3 start and end at A? Count a cycle and its reverse separately.

Graph G is shown.

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