Graph Theory Lessons

Answers to Lesson 7

  1. The the adjacency matrix of a null graph with n vertices is an n x n zero matrix.

  2. The adjacency matrix of the a complete graph has zeros on the main diagonal and ones everywhere else.

  3. The sum of the entries in row i of an adjacency matrix is equal to the degree of vertex i.

  4. Since the matrix is a 5 x 5 matrix, the graph has 5 vertices. If each row has three ones and two zeros then it means that each vertex has degree 3. This is impossible since it gives an odd number of odd degree vertices in the graph

  5. Columns 3 and 7 are swapped and also rows 3 and 7 are swapped.

  6. If a graph has adjacency matrix A, the trace of A3 is three times the number of triangles in the graph.
e-mail: C. Mawata

© C. Mawata