Graph Theory Lessons

The  adjacency matrix of a graph is an n x n matrix A = (a_i,j) in which the entry a_i,j =1 if there is an edge from vertex i to vertex j and is 0 if there is no edge from vertex i to vertex j. By the way, a matrix with only zeros and ones as entries is called a (0,1) matrix.

In the applet below draw a few graphs and the applet will display the adjacency matrix of a graph you draw.

To use the program Petersen to see the adjacency matrix of a graph, you should first get the program to draw the graph and then click Properties and then Adjacency Matrix.

1. Look at the adjacency matrix of the null graphs N₃, N₁₀, N₁₅. Describe the adjacency matrix of a null graph.
2. Look at the adjacency matrix of the complete graphs K₃, K₁₀, K₁₅. Describe the adjacency matrix of a complete graph.
3. Look at the adjacency matrices of a few more graphs. Give an interpretation for the sum of the entries in row i of an adjacency matrix.
4. Suppose you are told that the adjacency matrix for a simple graph has 5 rows and 5 columns. Suppose you are also told that each row contains three ones and two zeros, why is this impossible?
5. Get the adjacency matrix for a cube. It should look like figure 10

Fig. 10, The cube and its adjacency matrix


Now click Edit and then Swap labels. When you get the prompt "Enter first label" enter 3 and when it says "Enter second label" enter 7. You will see the graph re-drawn with the vertex labels 3 and 7 interchanged. Of course it is the same graph; only the names of the vertices are changed. Now look at the adjacency matrix again. Write it down and compare it to figure 10. What changes have occurred in the matrix? Notice that the adjacency matrix depends on how we choose to label the vertices of the graph. 

---

Recall from your algebra classes that you can (sometimes) multiply matrices together. When you multiply an adjacency matrix A by itself you get a new matrix A². Remember that if A is an n x n matrix and B=A² then the entries b_ij of B are obtained as
.

We shall see that b_ij is the number of paths of length 2 from i to j. (If i=j then you just get the degree of the vertex). How does this work? Let us start with an easy graph -- just three vertices labeled 1,2,3 and think about the quantity a_{1 2}*a₂₃. Here are the possibilities:

a1 2=1 and a2 3=1 so a1 2*a2 3=1

a1 2=0 and a2 3=1 so a1 2*a2 3=0

a1 2=1 and a2 3=0 so a1 2*a2 3=0

a1 2=0 and a2 3=0 so a1 2*a2 3=0


So we have that a_{1 2}*a_{2 3}=1 if there is a path from vertex 1 to vertex 3 via vertex 2 and is zero otherwise.

Now let us be more general: Consider any three vertices i, j, and k.We have that a_ik = 1 if there is an edge from i to k , otherwise a_ik = 0. (You can also say the same for a_kj). Now if you multiply a_ik and a_jk you get that a_ik * a_kj is either zero or one. It will be one if both a_ik and a_kj are one, otherwise it will be zero. So a_ik * a_kj = 1 if and only if there is a path of length 2 from vertex i to j via k and is zero otherwise. Notice that since in our adjacency matrices the diagonal entries are zero a_ii and a_jj are zero so when we get a_ik * a_kj = 1 the vertex k is neither i nor j. Now think about the sum

b_ij = a_i1*a_1j + a_i2*a_2j + a_i3*a_3jj+ ....+ a_in*a_nj

a_i1*a_1j contributes a 1 if there is a path of length 2 from i to j via 1 (and 0 if not)
a_i2*a_2j contributes a 1 if there is a path of length 2 from i to j via 2 (and 0 if not)
...
a_in*a_nj contributes a 1 if there is a path of length 2 from i to j via n (and 0 if not).

Have we counted them all? Sure because if there is a path from i to j of length 2 it must go via either vertex 1,2,3, ...or n so it must have been counted. Were any counted more than once? Surely not since a path of length 2 from i to j could not go via more than one vertex before getting to j -- it would have to be of length at least 3 to do that. This leads us to conclude that b_ij is the number of paths of length 2 from i to j.

Now that you get the idea you will understand the applet that follows: You will draw a graph in the left window and in the middle window will appear its adjacency matrix and then in the right window the square of its adjacency matrix. Play with it a while and discuss with your classmates to make sure you understand what all the numbers mean.


A graph, its adjacency matrix and the square of its adjacency matrix




6. The trace of a matrix is the sum of the elements along the main diagonal,
   .

   If a graph has adjacency matrix A, how is the trace of A³ related to the number of triangles in a graph?[Hint]

Answers

  

© C. Mawata