Adjacency matrices and graphs 3 5 4 Figure 2: An undirected graph with n = 5 vertices. For a given undirected graph G with no self-loops and at most one edge between any pair of nodes (i.e., a simple graph), as in Figure 2, we associate a n xn matrix A, such that Aij = 1 if there is an edge between node i and nodej, 0 otherwise. This matrix is called the adjacency matrix of the graph. The graph in Figure 2 has adjacency matrix A= 0 1 0 1 1 1 0 0 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 1. (2 points) Prove the following result: for positive integer k, the matrix Ak has an interesting inter- pretation: the entry in row i and column j gives the number of walks of length k (i.e., a collection of k edges) leading from vertex i to vertex j. Hint: prove this by induction on k, and look at the matrix-matrix product Ak-1 A. 2. (2 points) A triangle in a graph is defined as a subgraph composed of three vertices, where each vertex is reachable from each other vertex (i.e., a triangle forms a complete subgraph of order 3). In the graph of Figure 2, for example, nodes {1, 2, 4} form a triangle. Show that the number of triangles in G is equal to the trace of A divided by 6. Hint: For each node in a triangle in an undirected graph, there are two walks of length 3 leading from the node to itself, one corresponding to a clockwise walk, and the other to a counter-clockwise walk