Quiz #17
Quiz #17
Quiz #17
SOLUTIONS
Let the vertices of the graph are v1 , v2 , v3 , and v4 . The possible paths
between two of them, say v1 and v4 are:
v1 7→ v2 7→ v1 7→ v4 v1 7→ v2 7→ v3 7→ v4
v1 7→ v3 7→ v1 7→ v4 v1 7→ v3 7→ v2 7→ v4
v1 7→ v4 7→ v1 7→ v4 v1 7→ v4 7→ v2 7→ v4 v1 7→ v4 7→ v3 7→ v4
Let u1 and u4 be two fixed adjacent vertices from the graph. Assume that
the path is
u1 7→ u2 7→ u3 7→ u4 .
Then, the vertex u2 could be any of the three vertices adjacent to u1 and
nonadjacent to u4 , while (regardless of the choice of u2 ,) u3 could be any of
the three vertices adjacent to u4 and nonadjacent to u1 . That makes a total
of 3 · 3 = 9 possible paths.
Note that a solution using the adjacency matrix is also possible but it requires too much space
to be included here in full.
3
0 0 0 1 1 1 0 0 0 9 9 9
0 0 0 1 1 1 0 0 0 9 9 9
0 0 0 1 1 1 0 0 0 9 9 9
A =
3
1
=
1 1 0 0 0 9 9 9 0 0 0
1 1 1 0 0 0 9 9 9 0 0 0
1 1 1 0 0 0 9 9 9 0 0 0