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

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

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
2. (b) Q–R–S–T–Q
3. (c) Q–U–T–Q–R–S–T
4. (d) Q–R–S–Q–U–T–Q

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

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

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

The diagram shows the complete graph K6.

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 H is shown.

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