MATH/CSCI 2113
Assigment 5
Due Wednesday, February 27, at the beginning of class.

For each of the following problems, show your work.

1. Consider the graph $G$, given below. Form the adjacency matrix for this graph, and use this matrix to compute the number of walks of length 4 between all pairs of vertices.

   
   

   figure=graph3.eps, width=7cm

2. Consider the directed graph of section in the text book. Form the adjacency matrix for this graph, and use this matrix to compute (i) the number of walks of length 3 between all pairs of vertices, (ii) the number of common out-neighbours of each pair of vertices, and (iii) the number of common in-neighbours of each pair of vertices.
   figure=digraph4.eps, width=7cm

3. If $A$ is the adjacency matrix of a graph $G$, then what do the entries of the matrix $AA^TA$ represent? Explain your answer.

4. Draw all graphs with vertex set $\{ a,b,c,d\}$ and three edges. Indicate which of these graphs are isomorphic.

5. (a) Give an example of a graph so that the graph itself and its complement are both connected. (b) Give an example of a graph where the graph itself is connected, and its complement has two components.

6. (a) Given an example of a graph that is isomorphic to its complement. (b) Derive a formula (in terms of $n$, the number of vertices) for the number of edges in a graph that is isomorphic to its complement. Explain your answer.

7. Do problem 11.3.18 on page 504 of the text book.

8. Do problem 11.5.2 on page 529 of the text book.