Quiz #17

Download as pdf or txt
Download as pdf or txt
You are on page 1of 1

Quiz #17

SOLUTIONS

1. { 10 points } Find the number of paths of length 3 between


(a) two different vertices in K4 .

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

The problem can be solved also by using the adjacency matrix:


 3     
0 1 1 1 3 2 2 2 0 1 1 1 6 7 7 7
1 0 1 1  3 2 2    7
A3 =   =2  1 0 1 1  =  7 6 7 
1 1 0 1 2 2 3 2  1 1 0 1   7 7 6 7
1 1 1 0 2 2 2 3 1 1 1 0 7 7 7 6

(b) two adjacent vertices in K3,3 .

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

You might also like