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

Graph H is shown. List all the paths of length 3 from P to R.

• A path of length 3 uses 3 edges and 4 different vertices
• Start at P, take each neighbour in turn, and keep only the routes that reach R on the last edge without repeating a vertex
• P–Q–S–R; P–U–S–R

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

• A cycle of length 4 uses 4 different vertices, then returns to Q
• Start at Q and extend by one new vertex at a time. The last vertex must be adjacent to Q
• Q–R–U–T–Q; Q–S–T–U–Q; Q–T–U–R–Q; Q–U–T–S–Q

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

1. (a) U–Q–S–T–Q–S

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

2. (b) Q–R–S–T–Q

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

3. (c) Q–U–T–Q–R–S–T

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

4. (d) Q–R–S–Q–U–T–Q

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

Graph H is shown.

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

   • Degrees: P 2, Q 2, R 2, S 2, T 5, U 1
   • Odd: T and U

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 T
   • T–S–P–T–R–Q–T–U
   • It uses all 7 edges once: its length is 7

The graph shows the cable-car links between six stations. An edge means that two stations are joined by a direct link.

1. (a) List all the paths of length 3 from P to S.

   • Each path uses 3 edges and 4 different stops
   • P–Q–R–S; P–Q–T–S; P–U–T–S

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

   • Each cycle uses 4 different stops and returns to P
   • P–Q–T–U–P; P–U–T–Q–P

The graph shows the corridors of a school. A cleaner wants to walk along every corridor exactly once, and finish where she started.

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

   • Degrees: P 2, Q 4, R 2, S 2, T 2, U 2
   • All are even

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

   • With no odd vertices a trail can start anywhere and return to its start
   • P–Q–R–U–T–Q–S–P
   • It uses all 7 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
   • Q appears more than once, so it is not a cycle

A courier cycles between six shops. Each edge is a road. Here are three routes. Route 1: U–T–S–Q–P–T. Route 2: Q–R–S–T–P–Q. Route 3: P–Q–R–Q–S–R.

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 Q; 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 K6.

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 4
   • 4 × 3 = 12

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 5
   • 5 × 4 = 20

Graph H is shown.

1. (a) Find a trail from P to U that uses every edge exactly once.

   • Degrees: P 3, Q 2, R 4, S 2, T 4, U 1
   • Only P and U are odd, so the trail starts at P and ends at U
   • P–Q–R–P–T–S–R–T–U

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

   • Add the edge U–P at the end of the trail: P–Q–R–P–T–S–R–T–U–P
   • Every degree is now even, and the route returns to P
   • P–Q–R–P–T–S–R–T–U–P