AI HL · AHL 1
0 of 43 skills done
Walks, trails, paths, circuits and cycles
AHL 1.3
Press a vertex to start. Then press a vertex joined to where you are, again and again, to build a walk. The sentence says what kind of walk it is.
Press a vertex to start a walk.
List all the paths of length 3 from A to F in the graph. How many are there?
Have a go first. Then open the working one line at a time.
3 edges, 4 different vertices, from A to F
A path is a walk with no repeated vertex. Its length is the number of edges.
A has neighbours B and D. From B: C or D. From D: B or E.
Take each first step in turn, then each second step, and keep only routes that can reach F on the third edge.
Only C and E are adjacent to F
So the second vertex must lead to C or E.
A–B–C–F; A–D–E–F: 2 paths
Check that no vertex appears twice in any route.
List all the cycles of length 4 that start and end at C. Write a cycle and its reverse as two separate cycles.
Have a go first. Then open the working one line at a time.
A closed path: 4 different vertices, then back to C
A cycle starts and ends at the same vertex and repeats no other vertex.
B, E, F
The first step goes to one of these. The last step comes back from one of these.
C–B–D–E–C works, and so does its reverse C–E–D–B–C. C–F–E–D then needs an edge D–C, which does not exist.
Try each first step, then each second step, and check that the last vertex is adjacent to C.
C–B–D–E–C; C–E–D–B–C
The second is the first written backwards.
Find a trail in this graph that uses every edge exactly once. What is its length?
Have a go first. Then open the working one line at a time.
A 2, B 4, C 2, D 3, E 3
Only D and E have odd degree.
Start at D (or E)
A trail that uses every edge once can only start and end at the odd vertices. Pass through any other vertex and you use edges in pairs.
D–A–B–C–E–B–D–E
Cross off each edge as you use it. Back up and try again if you get stuck with edges unused.
7 edges, so length 7
The trail has 8 vertices in the list.
In the graph, a walk is B–C–E–D–B–A–D. Classify it as a walk, trail, path, circuit or cycle, giving the most specific name.
Have a go first. Then open the working one line at a time.
Each pair of neighbours in the list is joined by an edge
Check BC, CE, ED, DB, BA, AD in the graph.
BC, CE, ED, DB, BA, AD: all different
No edge is repeated, so it is a trail.
B and D appear twice
A vertex is repeated, so it is not a path.
Starts at B, ends at D
It is not closed, so it is not a circuit or a cycle. It is a trail.