Lecture 35 — Matrix Representations of Graphs

lecture
discrete-math
graph-theory

Two ways to write a graph down as a table of numbers. The adjacency matrix has a row and a column for each vertex and records how many edges join each pair of vertices. The incidence matrix has a row for each vertex and a column for each edge and records how many times each vertex is incident with each edge. Both go in both directions: a graph gives a matrix, and a matrix of the right kind gives a graph. Pre-work: Video 045 (Matrix Representations of Graphs). The definitions, how loops are counted, reading a graph off a matrix and which matrices qualify are in adjacency-matrices and incidence-matrices. Graphs, degree and the Handshake Theorem are in graphs.

Goals

  1. Learn how to represent a graph by an adjacency matrix.
  2. Learn how to represent a graph by an incidence matrix.
  3. Learn how to draw a graph from its adjacency matrix.
  4. Learn how to draw a graph from its incidence matrix.

Two questions to keep in mind:

  • In an incidence matrix, which are the rows and which are the columns: the vertices or the edges? The vertices are the rows and the edges are the columns, as in the definition. There is a way to remember it in which way round.
  • Is it OK to swap them? The swapped matrix holds the same information, but it is not the incidence matrix as this course defines it. Also in which way round.

The running example

One graph is used all the way through. It has vertex set \(\{v_1, v_2, v_3, v_4\}\) and edge set \(\{e_1, e_2, e_3, e_4, e_5\}\), with

Edge Endpoints
\(e_1\) \(\{v_2, v_3\}\)
\(e_2\) \(\{v_2, v_3\}\)
\(e_3\) \(\{v_1, v_2\}\)
\(e_4\) \(\{v_1, v_4\}\)
\(e_5\) \(\{v_4\}\)

So \(e_1\) and \(e_2\) are parallel edges, and \(e_5\) is a loop at \(v_4\). The degrees are \(\deg(v_1) = 2\), \(\deg(v_2) = 3\), \(\deg(v_3) = 2\) and \(\deg(v_4) = 3\), the loop adding 2 to \(\deg(v_4)\). They add to \(10 = 2 \cdot 5\).

Figure 1: The running example and its two matrices. The adjacency matrix A has a row and a column for each vertex, and each entry counts the edges joining that pair of vertices: the 2 is the pair of parallel edges between v2 and v3, and the 1 on the diagonal is the single loop at v4. The incidence matrix N has a row for each vertex and a column for each edge, and each entry counts how many times that vertex is incident with that edge: the 2 is the loop, which meets v4 at both of its ends.

Worked: edges between pairs of vertices

For the running example, how many edges have the following as endpoints?
(a) \(\{v_1, v_2\}\)
(b) \(\{v_1, v_3\}\)
(c) \(\{v_1, v_4\}\)
(d) \(\{v_2, v_3\}\)
(e) \(\{v_4\}\)

Endpoints Edges Number
(a) \(\{v_1, v_2\}\) \(e_3\) 1
(b) \(\{v_1, v_3\}\) none 0
(c) \(\{v_1, v_4\}\) \(e_4\) 1
(d) \(\{v_2, v_3\}\) \(e_1\), \(e_2\) 2
(e) \(\{v_4\}\) \(e_5\) 1

For (e), the set of endpoints \(\{v_4\}\) has one element, so the edges with that set of endpoints are the loops at \(v_4\). There is one, \(e_5\).

These five numbers are entries of the adjacency matrix. Answers (a), (b) and (c), with a 0 for “no loop at \(v_1\)”, are the first row, \(0\ 1\ 0\ 1\). Answer (d) is the entry in row \(v_2\), column \(v_3\), and answer (e) is the diagonal entry in row \(v_4\), column \(v_4\).

The adjacency matrix

The adjacency matrix of a graph with vertices \(v_1, v_2, \dots, v_n\) is the \(n \times n\) matrix \(A = [a_{ij}]\) where each entry \(a_{ij}\) is the number of edges with endpoints \(\{v_i, v_j\}\).

When \(i = j\) the set \(\{v_i, v_i\}\) is just \(\{v_i\}\), so a diagonal entry \(a_{ii}\) is the number of loops at \(v_i\). A loop is one edge, so it counts 1 on the diagonal. In the running example \(a_{44} = 1\) for the single loop \(e_5\).

Three things follow straight from the definition:

  • \(\{v_i, v_j\} = \{v_j, v_i\}\), so \(a_{ij} = a_{ji}\): the matrix is symmetric.
  • Every entry counts edges, so every entry is a non-negative integer.
  • A loop adds 2 to a degree but only 1 to the matrix. So \(\deg(v_i)\) is the row sum plus the diagonal entry. In the running example row \(v_4\) adds to \(1 + 0 + 0 + 1 = 2\), and \(\deg(v_4) = 2 + a_{44} = 3\).

More on all three, and the proofs, in adjacency-matrices.

Worked: write down the adjacency matrix

Write down the adjacency matrix for the graph below.

Figure 2: The graph for the first question: five vertices around a pentagon, two loops at v1, and two parallel edges between v5 and v2. It has 9 edges in all.

Answer.

\[A = \begin{array}{c|ccccc} & v_1 & v_2 & v_3 & v_4 & v_5 \\ \hline v_1 & 2 & 1 & 0 & 0 & 1 \\ v_2 & 1 & 0 & 1 & 0 & 2 \\ v_3 & 0 & 1 & 0 & 1 & 0 \\ v_4 & 0 & 0 & 1 & 0 & 1 \\ v_5 & 1 & 2 & 0 & 1 & 0 \end{array}\]

Go through the pairs once each, then copy across the diagonal, since the matrix is symmetric.

  • Diagonal. Two loops at \(v_1\), so \(a_{11} = 2\). No other vertex has a loop.
  • Row \(v_1\). One edge to \(v_2\), one to \(v_5\), none to \(v_3\) or \(v_4\).
  • Row \(v_2\). One edge to \(v_3\) and two parallel edges to \(v_5\), so \(a_{25} = 2\).
  • Rows \(v_3\) and \(v_4\). One edge \(v_3 v_4\) and one edge \(v_4 v_5\).

Two checks.

  • Edge count. Each edge is counted once in the upper triangle with the diagonal: \((2 + 1 + 0 + 0 + 1) + (0 + 1 + 0 + 2) + (0 + 1 + 0) + (0 + 1) + 0 = 4 + 3 + 1 + 1 + 0 = 9\), the 9 edges of the graph.
  • Degrees. Row sum plus diagonal entry: \(\deg(v_1) = 4 + 2 = 6\), the two loops giving 4 of it, and \(\deg(v_2) = 4\), \(\deg(v_3) = 2\), \(\deg(v_4) = 2\), \(\deg(v_5) = 4\). They add to \(18 = 2 \cdot 9\), as the graphs says they must.

Worked: draw the graph of an adjacency matrix

Draw the graph with this adjacency matrix. \[\begin{array}{c|ccccc} & v_1 & v_2 & v_3 & v_4 & v_5 \\ \hline v_1 & 2 & 1 & 0 & 3 & 1 \\ v_2 & 1 & 0 & 0 & 0 & 2 \\ v_3 & 0 & 0 & 0 & 1 & 0 \\ v_4 & 3 & 0 & 1 & 0 & 1 \\ v_5 & 1 & 2 & 0 & 1 & 0 \end{array}\]

First check that it can be an adjacency matrix: it is square, symmetric and its entries are non-negative integers. Then read only the diagonal and the entries above it. Each entry below the diagonal repeats one above it, and reading both would draw every edge twice.

Entry Value Edges
\(a_{11}\) 2 two loops at \(v_1\)
\(a_{12}\) 1 one edge \(v_1 v_2\)
\(a_{14}\) 3 three parallel edges \(v_1 v_4\)
\(a_{15}\) 1 one edge \(v_1 v_5\)
\(a_{25}\) 2 two parallel edges \(v_2 v_5\)
\(a_{34}\) 1 one edge \(v_3 v_4\)
\(a_{45}\) 1 one edge \(v_4 v_5\)

Every other entry on or above the diagonal is 0. That is \(2 + 1 + 3 + 1 + 2 + 1 + 1 = 11\) edges.

Figure 3: The graph drawn from the matrix: two loops at v1, three parallel edges between v1 and v4, two between v2 and v5, and single edges v1v2, v1v5, v3v4 and v4v5. The three v1v4 edges cross the two v2v5 edges, but crossings are not vertices. The degrees, in red, are each row sum plus the diagonal entry, so v1 has degree 7 + 2 = 9. They add to 22, twice the 11 edges.

The degrees are \(\deg(v_1) = 7 + 2 = 9\), \(\deg(v_2) = 3\), \(\deg(v_3) = 1\), \(\deg(v_4) = 5\) and \(\deg(v_5) = 4\), a total of \(22 = 2 \cdot 11\). Where the vertices go on the page is free. The matrix fixes only which vertices are joined, and how many times.

Worked: which is an adjacency matrix

Which of the following is an adjacency matrix for a graph?
A. \(\begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix}\)
B. \(\begin{bmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \end{bmatrix}\)
C. \(\begin{bmatrix} 73 \end{bmatrix}\)
D. \(\begin{bmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 2 & 2 \\ 0 & 2 & 0 & 0 \\ 1 & 1 & 0 & 1 \end{bmatrix}\)

Answer: C.

A matrix is an adjacency matrix of some graph exactly when it is square, symmetric and has non-negative integer entries (adjacency-matrices).

  • A is square and symmetric, but \(-1\) cannot be a number of edges.
  • B is \(2 \times 3\). An adjacency matrix has one row and one column for each vertex, so it is always square.
  • C is \(1 \times 1\), trivially symmetric, and 73 is a non-negative integer. It is the graph with one vertex and 73 loops. That vertex has degree \(73 + 73 = 146\), and the graph has 73 edges.
  • D is square with non-negative integer entries, but not symmetric: \(a_{24} = 2\) and \(a_{42} = 1\). The number of edges between \(v_2\) and \(v_4\) cannot be both 2 and 1. Every other pair matches across the diagonal; this one pair is enough.

Figure 4: The graph of the 1 by 1 matrix [73]: a single vertex with 73 loops, three of them drawn and the dashed one standing for the rest. Its one diagonal entry counts the loops, 73, and its degree is twice that, 146.

Worked: how many times is a vertex incident with an edge

For the running example:
(a) How many times is \(v_1\) incident with \(e_1\)?
(b) How many times is \(v_1\) incident with \(e_4\)?
(c) How many times is \(v_2\) incident with \(e_2\)?
(d) How many times is \(v_4\) incident with \(e_5\)?

(a) 0. The endpoints of \(e_1\) are \(v_2\) and \(v_3\), so \(e_1\) does not meet \(v_1\).

(b) 1. \(e_4\) joins \(v_1\) and \(v_4\). One of its ends is at \(v_1\).

(c) 1. \(e_2\) joins \(v_2\) and \(v_3\). One of its ends is at \(v_2\).

(d) 2. \(e_5\) is a loop at \(v_4\). Both of its ends are at \(v_4\), so it meets \(v_4\) twice. This is the same count that makes a loop add 2 to a degree (graphs).

The incidence matrix

The incidence matrix of a graph with vertices \(v_1, v_2, \dots, v_n\) and edges \(e_1, e_2, \dots, e_m\) is the \(n \times m\) matrix \(N = [n_{ij}]\) where each entry \(n_{ij}\) is the number of times vertex \(v_i\) is incident with edge \(e_j\).

The answers above are four of its entries: \(n_{11} = 0\), \(n_{14} = 1\), \(n_{22} = 1\) and \(n_{45} = 2\). The whole matrix for the running example is in the figure.

  • A column is an edge. It has a 1 at each of the edge’s two endpoints, or a single 2 at the vertex of a loop. Either way every column adds to 2: every edge has two ends.
  • A row is a vertex. It adds up the ends of edges at that vertex, so the row sum is the degree, loops included. In the running example the rows add to \(2, 3, 2, 3\).
  • Parallel edges are identical columns. The columns of \(e_1\) and \(e_2\) are both \((0, 1, 1, 0)\).

Adding up all the entries by columns gives \(2m\), and by rows gives the sum of the degrees. That is the graphs again. More in incidence-matrices.

Which way round

Rows are vertices, columns are edges. One way to remember it: the entry \(n_{ij}\) answers “how many times is vertex \(v_i\) incident with edge \(e_j\)”, and the index that comes first, \(i\), is the row, so the vertex comes first. Another: the adjacency matrix has a row for each vertex, and so does the incidence matrix. Both matrices have \(n\) rows, one per vertex; they differ only in their columns, vertices for \(A\) and edges for \(N\).

Swapping them gives the transpose \(N^{\mathsf T}\), the \(m \times n\) matrix with a row for each edge. It holds exactly the same information. The graph can be rebuilt from it just as well, with every row adding to 2 and every column adding to a degree. But it is not the incidence matrix as this course defines it. When asked for the incidence matrix, put the vertices down the side and the edges across the top, and label both.

The question does not arise for the adjacency matrix, because it is symmetric: swapping rows and columns gives the same matrix. What does matter for both is the order of the vertices, and for \(N\) the order of the edges. A different order permutes the rows or columns and gives a different matrix for the same graph, which is why the rows and columns should always be labelled.

Worked: write down the incidence matrix

Write down the incidence matrix for the graph below.

Figure 5: The graph for the incidence-matrix question: a loop e1 at v1, two parallel edges e2 and e3 between v5 and v2, an edge e4 from v5 to v4, and an isolated vertex v3. The loop gives v1 the entry 2 in column e1, and v3, which meets no edge, gives a row of zeros.

Answer.

\[N = \begin{array}{c|cccc} & e_1 & e_2 & e_3 & e_4 \\ \hline v_1 & 2 & 0 & 0 & 0 \\ v_2 & 0 & 1 & 1 & 0 \\ v_3 & 0 & 0 & 0 & 0 \\ v_4 & 0 & 0 & 0 & 1 \\ v_5 & 0 & 1 & 1 & 1 \end{array}\]

Fill it one column, one edge, at a time.

  • \(e_1\) is a loop at \(v_1\): a 2 in row \(v_1\) and 0 elsewhere.
  • \(e_2\) and \(e_3\) both join \(v_5\) and \(v_2\): a 1 in rows \(v_2\) and \(v_5\). Being parallel, they give the same column.
  • \(e_4\) joins \(v_5\) and \(v_4\): a 1 in rows \(v_4\) and \(v_5\).

Checks. Every column adds to 2. The row sums are the degrees, \(2, 2, 0, 1, 3\), adding to \(8 = 2 \cdot 4\). The row of \(v_3\) is all zeros, because \(v_3\) is isolated: a vertex still gets its row even when no edge meets it.

Worked: draw the graph of an incidence matrix

Draw the graph with this incidence matrix. \[\begin{array}{c|cccc} & e_1 & e_2 & e_3 & e_4 \\ \hline v_1 & 2 & 1 & 0 & 0 \\ v_2 & 0 & 1 & 0 & 0 \\ v_3 & 0 & 0 & 2 & 0 \\ v_4 & 0 & 0 & 0 & 1 \\ v_5 & 0 & 0 & 0 & 1 \end{array}\]

Every column adds to 2, so it is an incidence matrix. Read it one column at a time. A column with two 1s is an edge between those two vertices, and a column with a single 2 is a loop.

Column Entries Edge
\(e_1\) 2 at \(v_1\) loop at \(v_1\)
\(e_2\) 1 at \(v_1\), 1 at \(v_2\) \(v_1 v_2\)
\(e_3\) 2 at \(v_3\) loop at \(v_3\)
\(e_4\) 1 at \(v_4\), 1 at \(v_5\) \(v_4 v_5\)

Figure 6: The graph drawn from the incidence matrix: each column is one edge. Columns e1 and e3 each have a single 2, so they are loops, at v1 and at v3. Columns e2 and e4 each have two 1s, so they join v1 to v2 and v4 to v5. The graph falls into three pieces. The row sums 3, 1, 2, 1, 1 are the degrees, and add to 8, twice the 4 edges.

Worked: which is an incidence matrix

Which of the following is an incidence matrix for a graph?
A. \(\begin{bmatrix} 1 & 0 \\ 0 & 3 \end{bmatrix}\)
B. \(\begin{bmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \end{bmatrix}\)
C. \(\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}\)
D. \(\begin{bmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 2 & 2 \\ 0 & 2 & 0 & 0 \\ 1 & 1 & 0 & 1 \end{bmatrix}\)

Answer: B.

A matrix is an incidence matrix of some graph exactly when its entries are non-negative integers and every column adds to 2, so that each column is either two 1s or a single 2 (incidence-matrices). Check the columns.

Column sums Verdict
A \(1,\ 3\) no: the first column is an edge with one end, and no vertex can meet an edge 3 times
B \(2,\ 2,\ 2\) yes
C \(1,\ 1\) no: each column is an edge with only one end
D \(2,\ 4,\ 2,\ 4\) no: columns 2 and 4 would be edges with four ends

B has two rows and three columns, so two vertices and three edges, and each column \((1, 1)\) is an edge joining the two vertices. It is two vertices joined by three parallel edges.

In C a column with a single 1 is not a loop: a loop meets its vertex twice and is a single 2. In D the first and third columns are fine on their own, an edge \(v_2 v_4\) and a loop at \(v_2\), but one bad column is enough to rule a matrix out. A square shape, or symmetry, has nothing to do with it: B is not square, and C is square and symmetric.

Figure 7: The graph of matrix B: two vertices and three edges. Each column of B is (1, 1), a 1 at each vertex, so each edge joins v1 and v2. The three columns are identical, which is exactly what three parallel edges look like in an incidence matrix.

Worked: Eulerian from the incidence matrix

For each of the following incidence matrices, determine whether the associated graph \(G\) is Eulerian. Explain why or why not. \[\text{(a)}\ \ N = \begin{array}{c|cccccc} & e_1 & e_2 & e_3 & e_4 & e_5 & e_6 \\ \hline v_1 & 1 & 1 & 0 & 0 & 0 & 0 \\ v_2 & 1 & 0 & 1 & 1 & 0 & 1 \\ v_3 & 0 & 1 & 1 & 0 & 1 & 1 \\ v_4 & 0 & 0 & 0 & 1 & 1 & 0 \end{array} \qquad \text{(b)}\ \ N = \begin{array}{c|cccc} & a & b & c & d \\ \hline u & 1 & 0 & 1 & 0 \\ v & 0 & 1 & 0 & 1 \\ w & 0 & 1 & 0 & 1 \\ x & 1 & 0 & 1 & 0 \end{array}\]

A graph is Eulerian if it has an Euler circuit, a circuit that contains every edge (euler-circuits-and-trails). The test is the theorem (euler-circuits-and-trails):

A connected graph has an Euler circuit if and only if every vertex has even degree.

The incidence matrix gives both halves of the test. The degrees are the row sums, and the columns say which vertices each edge joins, which settles whether the graph is connected.

(a) Yes, \(G\) is Eulerian.

The row sums give the degrees:

\[\deg(v_1) = 2, \quad \deg(v_2) = 4, \quad \deg(v_3) = 4, \quad \deg(v_4) = 2.\]

All four are even. Reading the columns, the edges are \(e_1 = v_1 v_2\), \(e_2 = v_1 v_3\), \(e_3 = v_2 v_3\), \(e_4 = v_2 v_4\), \(e_5 = v_3 v_4\) and \(e_6 = v_2 v_3\), so \(e_3\) and \(e_6\) are parallel. \(G\) is connected: \(v_2\) is joined to each of \(v_1\), \(v_3\) and \(v_4\). A connected graph with every degree even has an Euler circuit, for example

\[v_1\ e_1\ v_2\ e_3\ v_3\ e_6\ v_2\ e_4\ v_4\ e_5\ v_3\ e_2\ v_1.\]

It uses \(e_1, e_3, e_6, e_4, e_5, e_2\), each of the six edges exactly once, each edge joins the vertices on either side of it in the list, and it ends where it started.

(b) No, \(G\) is not Eulerian.

Every row adds to 2, so every vertex has even degree. But the columns show the edges are \(a = ux\), \(b = vw\), \(c = ux\) and \(d = vw\). No edge joins \(u\) or \(x\) to \(v\) or \(w\), so \(G\) is not connected: it is two separate pieces, \(u\) and \(x\) joined by \(a\) and \(c\), and \(v\) and \(w\) joined by \(b\) and \(d\). A circuit is a walk, and a walk only moves along edges, so it never leaves the piece it starts in. No circuit can contain both \(a\) and \(b\), so there is no Euler circuit. Even degrees are not enough on their own: the theorem needs the graph to be connected.

Figure 8: The two graphs read off the incidence matrices, degrees in red. Left, (a): every degree is even and the graph is connected, so it has an Euler circuit; the diagonals e2 and e4 cross without meeting. Right, (b): every degree is 2, but the graph is two separate pieces, and a circuit cannot get from one piece to the other, so no circuit uses every edge.

See also