Consider the graph

(a) Compute A4, A6, A8 and answer the questions in part (b) for walks of lengths 4, 6, and 8. Make a conjecture as to when there will be no walks of even length from vertex Vi to vertex Vj.
(b) Compute A3, A5, A7 and answer the questions from part (b) for walks of lengths 3, 5, and 7. Does your conjecture from part (c) hold for walks of odd length? Explain. Make a conjecture as to whether there are any walks of length k from Vi to Vj based on whether i + j + k is odd or even.
(c) If we add the edges {V3, V6}, {V5, V8} to the graph, the adjacency matrix B for the new graph can be generated by setting B = A and then setting
8(3, 6) = 1, B(6, 3) = 1, B(5, 8) = 1, 6(8, 5) = I
Compute Bk, for k = 2, 3, 4, 5. Is your conjecture from part (d) still valid for the new graph?
(d) Add the edge {V6, V8} to the figure and construct the adjacency matrix C for the resulting graph. Compute powers of C to determine whether your conjecture from part (d) will still hold for this new graph.

Transcribed Image Text:

Va Vi