Counting walks with powers of the adjacency matrix Problem set A

The graph has five vertices. Find the number of walks of length 3:

1. (a) from P to Q;
2. (b) from Q to S.

The graph has vertices A, B, C and D. There is a loop at C, a double edge BC, and single edges AB, CD and DA. Enter the loop as 1. Find the number of walks of length 4:

1. (a) from A to C.

The directed graph shows one-way links. Find the number of walks of length 3:

1. (a) from X to W;
2. (b) from Y to W.

The directed graph shows one-way links. Find the number of walks of length less than 4:

1. (a) from G to E;
2. (b) from H to F.

In the graph, a path visits no vertex twice. A cycle and its reverse count as one cycle.

1. (a) List all the paths of length 3 from A to D.
2. (b) List all the cycles of length 4 that start and end at B.

Decide whether the graph is Eulerian or semi-Eulerian, and find an Eulerian circuit or trail.

Five islands A to E are joined by ferry routes. Two companies run a ferry between A and B, so there are two routes there. Each other pair joined on the map has one route. A trip is a sequence of ferry crossings. Find the number of walks of length 4:

1. (a) from A to D;
2. (b) from C to E.

A courier drives along one-way streets between five junctions A to E, as shown. Find the number of walks of length less than 4:

1. (a) from A to E;
2. (b) from B to E.

The graph is simple (no loops, no repeated edges) with adjacency matrix A.

1. (a) Find \(A^2\) and write down its diagonal. Compare it with the degrees of the vertices.
2. (b) Use your answer to find the number of edges in the graph.

The directed graph shows one-way links between four vertices. Find the smallest k for which there are more than 5 walks of length k from J to L.