8.02 Degree and adjacency matrices

The degree of a vertex is the number of edges that either go into or out of a vertex, where loops are counted twice. This number tells us how many ways we can move from that vertex to another (or even the same) vertex within the network.

A useful trick is to make a ring close around the vertex - count up the number of times that edges cross the ring at a vertex, and you’ll have the degree:

Each vertex has a small ring placed around it, and the number of crossings are counted up. If you do it this way you’ll always remember to count loops twice.

Examples

Example 1

Consider this network:

a

What is the degree of vertex C?

Worked Solution

Create a strategy

Count the number of edges going into or out of vertex C.

Apply the idea

Vertex C is only connected by one edge.

The degree of vertex C is 1.

b

What is the degree of vertex D?

Worked Solution

Create a strategy

Count the number of edges going into or out of vertex D.

Apply the idea

Vertex D is connected to three edges.

The degree of vertex D is 3.

It is sometimes useful to use a table (its proper name is the adjacency matrix) to represent a network. This is a square array of numbers, one row and column for each vertex, that records how many connections there are between the vertices. For an undirected network, the entry for a particular row and column represents the number of edges connecting the matching vertices.

Here’s a simple network with 5 vertices.

Now we can create a table, with one row and column for each vertex:

\begin{matrix} & \begin{matrix} A&B&C&D&E\end{matrix}\\ \begin{matrix} A \\ B \\ C \\ D \\ E \end{matrix} & \begin{bmatrix} \,\, . \, &\,\,.\, &\,\,.\, &\,\,.\, &\,.\,\, \\ \,\, . \, &\,\,.\, &\,\,.\, &\,\,.\, &\,.\,\, \\ \,\, . \, &\,\,.\, &\,\,.\, &\,\,.\, &\,.\,\, \\ \,\, . \, &\,\,.\, &\,\,.\, &\,\,.\, &\,.\,\, \\ \,\, . \, &\,\,.\, &\,\,.\, &\,\,.\, &\,.\,\, \end{bmatrix} \end{matrix}

Then we put the number edges connecting two vertices as the corresponding table entry. Let’s start by filling out the first row by putting a 1 if it is connected to A, and a 0 if it isn’t.

\begin{matrix} & \begin{matrix} A&B&C&D&E\end{matrix}\\ \begin{matrix} A \\ B \\ C \\ D \\ E \end{matrix} & \begin{bmatrix} \, 0 &\, 1 &\, 1 &\, 1 &\, 1 \\ \,\, . \, &\,\,.\, &\,\,.\, &\,\,.\, &\,.\,\, \\ \,\, . \, &\,\,.\, &\,\,.\, &\,\,.\, &\,.\,\, \\ \,\, . \, &\,\,.\, &\,\,.\, &\,\,.\, &\,.\,\, \\ \,\, . \, &\,\,.\, &\,\,.\, &\,\,.\, &\,.\,\, \end{bmatrix} \end{matrix}

0 comes first because A isn’t connected to itself (there’s no loop at A), and A is connected to B, \, C, \, D, and E, so we put a 1 for each other entry in the table.

Since these edges are undirected, we can fill out the first column with the same numbers - if A is connected to B, then B is connected to A, and so on:

\begin{matrix} & \begin{matrix} A&B&C&D&E\end{matrix}\\ \begin{matrix} A \\ B \\ C \\ D \\ E \end{matrix} & \begin{bmatrix} \, 0 &\, 1 &\, 1 &\, 1 &\, 1 \\ \, 1 &\,\,.\, &\,\,.\, &\,\,.\, &\,.\,\, \\ \, 1 &\,\,.\, &\,\,.\, &\,\,.\, &\,.\,\, \\ \, 1 &\,\,.\, &\,\,.\, &\,\,.\, &\,.\,\, \\ \, 1 &\,\,.\, &\,\,.\, &\,\,.\, &\,.\,\, \end{bmatrix} \end{matrix}

Now to fill out the second row, we notice that B is connected to A (already recorded), not itself (no loop), and it is connected to C, \, D, and E:

\begin{matrix} & \begin{matrix} A&B&C&D&E\end{matrix}\\ \begin{matrix} A\\ B\\ C\\D\\E \end{matrix} & \begin{bmatrix} \, 0 &\, 1 &\, 1 &\, 1 &\, 1 \\ \, 1 &\, 0 &\, 1 &\, 1 &\, 1 \\ \, 1 &\,\,1\, &\,\,.\, &\,\,.\, &\,.\,\, \\ \, 1 &\,\,1\, &\,\,.\, &\,\,.\, &\,.\,\, \\ \, 1 &\,\,1\, &\,\,.\, &\,\,.\, &\,.\,\, \end{bmatrix} \end{matrix}

We then record the remaining connections between C, \, D, and E in the same way:

\begin{matrix} & \begin{matrix} A&B&C&D&E\end{matrix}\\ \begin{matrix} A\\ B\\ C\\ D \\E \end{matrix} & \begin{bmatrix} \, 0 &\, 1 &\, 1 &\, 1 &\, 1 \\ \, 1 &\, 0 &\, 1 &\, 1 &\, 1 \\ \, 1 &\, 1 &\, 0 &\, 1 &\, 0 \\ \, 1 &\, 1 &\, 1 &\, 0 &\, 0 \\ \, 1 &\, 1 &\, 0 &\, 0 &\, 0 \end{bmatrix} \end{matrix}

This is our completed table. Notice that:

• The diagonal running top-left to bottom-right (called the main diagonal) has only 0's. This represents how no edge is connected to itself in the network - there are no loops.

• The numbers not on the main diagonal are only 0's and 1's. This represents how no vertex is connected to any other by more than one edge.

All adjacency matrices representing simple networks will have these features.

As an added bonus the sum of all the entries in a row (or column) gives us the degree of the corresponding vertex - we can tell from the table that C and E have degree 2, \, D has degree 3, and A and B have degree 4. This trick doesn't work if the network has loops, though - in this case, numbers on the main diagonal need to be doubled, to make sure they're counted twice.

Examples

Example 2

Fill in the adjacency matrix for this network:

a

\begin{matrix} & \begin{matrix} A&B&C&D \end{matrix}\\ \begin{matrix} A \\ B \\ C \\ D \end{matrix} & \begin{bmatrix} ⬚ &⬚ &⬚ &⬚ \\ ⬚ &⬚ &⬚ &⬚ \\ ⬚ &⬚ &⬚ &⬚ \\ ⬚ &⬚ &⬚ &⬚ \end{bmatrix} \end{matrix}

Worked Solution

Create a strategy

For each box, count the number of edges that connects the row vertex and the column vertex together. Write 1 if it is connected to the vertex and 0 if it isn’t.

Apply the idea

The given network is an undirected network, so each edge connects in both directions. This means that the adjacency matrix is symmetric about the main diagonal.

Starting in the top left, we write 0 first because A isn’t connected to itself. Next, we write 1 since A is connected to B and 0 for each other entry in the matrix because A is not connected to C and D.

\begin{matrix} & \begin{matrix} A&B&C&D \end{matrix}\\ \begin{matrix} A \\ B \\ C \\ D \end{matrix} & \begin{bmatrix} \,\, 0 &\, 1 \,&\, 0 \,&\, 0 \,\, \\ ⬚ &⬚ &⬚ &⬚ \\ ⬚ &⬚ &⬚ &⬚ \\ ⬚ &⬚ &⬚ &⬚ \end{bmatrix} \end{matrix}

Next, we fill out the first column with the same numbers as the first row.

\begin{matrix} & \begin{matrix} A&B&C&D \end{matrix}\\ \begin{matrix} A \\ B \\ C \\ D \end{matrix} & \begin{bmatrix} \,\, 0 &\, 1 \,&\, 0 \,&\, 0 \,\, \\ \,\, 1 &⬚ &⬚ &⬚ \\ \,\, 0 &⬚ &⬚ &⬚ \\ \,\, 0 &⬚ &⬚ &⬚ \end{bmatrix} \end{matrix}

The network shows that B is connected to A and C but not to itself or to D. So we have the following in the second row:

\begin{matrix} & \begin{matrix} A&B&C&D \end{matrix}\\ \begin{matrix} A \\ B \\ C \\ D \end{matrix} & \begin{bmatrix} \,\, 0 &\, 1 \,&\, 0 \,&\, 0 \,\, \\ \,\, 1 &\, 0 \,&\, 1 \,&\, 0 \,\, \\ \,\, 0 &⬚ &⬚ &⬚ \\ \,\, 0 &⬚ &⬚ &⬚ \end{bmatrix} \end{matrix}

Now we write the remaining connections between C and D in the same way. So we have the adjacency matrix for this network.

\begin{matrix} & \begin{matrix} A&B&C&D \end{matrix}\\ \begin{matrix} A \\ B \\ C \\ D \end{matrix} & \begin{bmatrix} \,\, 0 &\, 1 \,&\, 0 \,&\, 0 \,\, \\ \,\, 1 &\, 0 \,&\, 1 \,&\, 0 \,\, \\ \,\, 0 &\, 1 \,&\, 0 \,&\, 1 \,\, \\ \,\, 0 &\, 0 \,&\, 1 \,&\, 0 \,\, \end{bmatrix} \end{matrix}

b

What is the degree of vertex A?

Worked Solution

Create a strategy

Count the number of edges connected to the indicated vertex.

Apply the idea

The degree of vertex A is 1.

Reflect and check

Since the given network is simple, the degree of A will be the sum of the numbers in the first column.

\displaystyle \text{Degree}	\displaystyle =	\displaystyle 0+1+0+0	Add the numbers from the first column
	\displaystyle =	\displaystyle 1	Evaluate

Now for a directed network, the entry in a particular row and column indicates the number of edges going from the corresponding row vertex to the corresponding column vertex.

Here’s a directed, non-simple network with 5 vertices and its corresponding table:

This table looks a little different from the last one. Notice that:

• The matrix is not symmetrical across the main diagonal (an edge from A to B can exist without an edge from B to A),

• There is a 1 on the main diagonal (there is a loop at C), and

• There’s a 2 in the table (there are two edges from D to E).

While an asymmetrical matrix means the network is directed, there are directed networks that produce symmetrical tables.

Up until now we have been using networks to make adjacency matrices. But we can go back the other way - the information in these tables, and knowing whether the network is directed or undirected, is enough for us to create the network.

Here’s a table with 6 rows and columns (so there are 6 vertices in the network), and we are also told that the network is undirected.

\begin{bmatrix} 1&1&1&0&1&0 \\1&0&2&1&1&1 \\1&2&0&0&0&0 \\0&1&0&1&1&0 \\1&1&0&1&0&1 \\0&1&1&0&1&0 \end{bmatrix}

This is a representation of the network that we get when we draw it out:

• start with the first row, and the vertex on the left

• draw in the edges connected to that vertex

• move on to the next row/next vertex clockwise, ignoring the numbers below the main diagonal - they get drawn into the network when we do earlier rows for undirected networks. If the graph is directed, all the numbers need to be turned into edges.

Examples

Example 3

Consider the following network:

a

Fill in the adjacency matrix for this network:\begin{matrix} & \begin{matrix} P&Q&R&S \end{matrix}\\ \begin{matrix} P \\ Q \\ R \\ S \end{matrix} & \begin{bmatrix} ⬚ &⬚ &⬚ &⬚ \\ ⬚ &⬚ &⬚ &⬚ \\ ⬚ &⬚ &⬚ &⬚ \\ ⬚ &⬚ &⬚ &⬚ \end{bmatrix} \end{matrix}

Worked Solution

Create a strategy

For each box, write the number of edges that connect the vertex in that row and the vertex in that column.

Apply the idea

The given network is an undirected network, so each edge connects in both directions. This means that the adjacency matrix is symmetric about the main diagonal.

Vertex P is connected to itself and vertices Q and R. So we write a 1 under P, \, Q, and R, and a 0 under S.

\begin{matrix} & \begin{matrix} P&Q&R&S \end{matrix}\\ \begin{matrix} P \\ Q \\ R \\ S \end{matrix} & \begin{bmatrix} \,\, 1 &\, 1 \,&\, 1 \,&\, 0 \,\, \\ ⬚ &⬚ &⬚ &⬚ \\ ⬚ &⬚ &⬚ &⬚ \\ ⬚ &⬚ &⬚ &⬚ \end{bmatrix} \end{matrix}

Next, we fill out the first column with the same numbers as the first row in the same order.

\begin{matrix} & \begin{matrix} P&Q&R&S \end{matrix}\\ \begin{matrix} P \\ Q \\ R \\ S \end{matrix} & \begin{bmatrix} \,\, 1 &\, 1 \,&\, 1 \,&\, 0 \,\, \\ \,\, 1 &⬚ &⬚ &⬚ \\ \,\, 1 &⬚ &⬚ &⬚ \\ \,\, 0 &⬚ &⬚ &⬚ \end{bmatrix} \end{matrix}

To fill out the second row, we notice that Q is only connected to P. So we put a 1 under P and 0s for the rest. We can then write the same numbers in column Q.

\begin{matrix} & \begin{matrix} P&Q&R&S \end{matrix}\\ \begin{matrix} P \\ Q \\ R \\ S \end{matrix} & \begin{bmatrix} \,\, 1 &\, 1 \,&\, 1 \,&\, 0 \,\, \\ \,\, 1 &\, 0 \,&\, 0 \,&\, 0 \,\, \\ \,\, 1 &0 &⬚ &⬚ \\ \,\, 0 &0 &⬚ &⬚ \end{bmatrix} \end{matrix}

Continuing in the same way, since R and S are connected, and there is a loop at vertex S, we have the following adjacency matrix for the network.

\begin{matrix} & \begin{matrix} P&Q&R&S \end{matrix}\\ \begin{matrix} P \\ Q \\ R \\ S \end{matrix} & \begin{bmatrix} \,\, 1 &\, 1 \,&\, 1 \,&\, 0 \,\, \\ \,\, 1 &\, 0 \,&\, 0 \,&\, 0 \,\, \\ \,\, 1 &\, 0 \,&\, 0 \,&\, 1 \,\, \\ \,\, 0 &\, 0 \,&\, 1 \,&\, 1 \,\, \end{bmatrix} \end{matrix}

b

What is the degree of vertex P?

Worked Solution

Create a strategy

Add the entries in the column corresponding to the vertex in the adjacency matrix, double the number on the main diagonal for vertices with loops.

Apply the idea

The network has a loop at P, so we first need to double the number in the first row.

\displaystyle \text{Degree}	\displaystyle =	\displaystyle 2\times 1+1+1+0	Use the numbers from the first column
	\displaystyle =	\displaystyle 4	Evaluate

There are many different but equivalent representations of a graph. Rearranging the vertices and edges while maintaining the same connectivity retains the underlying structure of a graph. This is known as an isomorphic graph.

Two graphs are isomorphic if each of the following is true:

1. They have the same number of vertices.

2. They have the same number of edges.

3. They have a matching number of vertices of each degree.

4. Corresponding vertices connect in the same way.

Let us determine if the two graphs below are isomorphic.

Both graphs have the same number of vertices and edges. However, the graph on the right has a vertex of degree 2 in the top right, whereas the graph on the left has no vertex of degree 2. So, there cannot be a way to rearrange the two graphs to look like each other.

So the two graphs are not isomorphic.

If it is not quick to spot the graphs have a mismatched vertex of a particular degree, it is a good idea to list the degree for each vertex in the graph. If we create a list from largest to smallest this is known as the degree sequence of the graph and makes for easy comparison. For example, the graph on the left has the degree sequence \left(4, 3, 3, 3, 3\right) and the graph on the right has degree sequence \left(4, 4, 3, 3, 2\right). By quick comparison the sequences are not equal and therefore, the graphs are not isomorphic. If the sequences were equal we would then need to check the connections were equivalent, this can be a complex task for large networks.