Adjacency Matrices

definitions
discrete-math
graph-theory

An adjacency matrix writes a graph down as a square table of numbers: a row and a column for each vertex, and in each place the number of edges joining that pair of vertices. It records everything about the graph except the names of the edges, so the graph can be redrawn from it, and the degrees, and with them whether the graph has an Euler circuit, can be read straight off it. The one trap is the loop, which counts 1 in the matrix but 2 in the degree. The other matrix of a graph, with a row for each vertex and a column for each edge, is in incidence-matrices. Graphs, loops, degree and the Handshake Theorem are in graphs. First met in 2026-10-27-matrix-representations-of-graphs.

Definition

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\}\).

Figure 1: A graph and its adjacency matrix. Each entry counts the edges joining the vertex of its row to the vertex of its column: the 2 in row v2, column v3 is the two parallel edges e1 and e2, and the 0 in row v1, column v3 says v1 and v3 are not adjacent. The diagonal counts loops, so the single loop e5 gives a 1 in row v4, column v4. Every entry appears again reflected in the diagonal, because the edges between v2 and v3 are the edges between v3 and v2.

What the definition gives straight away:

  • \(A\) is square, \(n \times n\), with one row and one column for each vertex.
  • Every entry is a non-negative integer, since it counts edges.
  • \(A\) is symmetric: \(a_{ij} = a_{ji}\) for all \(i, j\). The set \(\{v_i, v_j\}\) is the same set as \(\{v_j, v_i\}\), so the two entries count the same edges. Everything below the diagonal repeats something above it.
  • Off the diagonal, \(a_{ij} \ge 1\) exactly when \(v_i\) and \(v_j\) are adjacent, and \(a_{ij} \ge 2\) exactly when they are joined by parallel edges.
  • On the diagonal, \(a_{ii}\) is the number of loops at \(v_i\). See loops.
  • An isolated vertex has a row and a column of zeros. It still gets its row, because the matrix has one for every vertex.

Simple graphs. A graph is simple when it has no loops and no parallel edges (graphs). In the matrix that is: every entry is 0 or 1, and the diagonal is all 0. The complete graph \(K_4\), for example, has a 1 in every place off the diagonal:

\[\begin{array}{c|cccc} & v_1 & v_2 & v_3 & v_4 \\ \hline v_1 & 0 & 1 & 1 & 1 \\ v_2 & 1 & 0 & 1 & 1 \\ v_3 & 1 & 1 & 0 & 1 \\ v_4 & 1 & 1 & 1 & 0 \end{array}\]

The matrix depends on the order of the vertices. Listing the same vertices in a different order rearranges the rows and the columns in the same way. With the vertices of the graph above in the order \(v_2, v_3, v_1, v_4\), the matrix is

\[\begin{array}{c|cccc} & v_2 & v_3 & v_1 & v_4 \\ \hline v_2 & 0 & 2 & 1 & 0 \\ v_3 & 2 & 0 & 0 & 0 \\ v_1 & 1 & 0 & 0 & 1 \\ v_4 & 0 & 0 & 1 & 1 \end{array}\]

a different matrix for the same graph. So a graph has an adjacency matrix for each order of its vertices, and the rows and columns should always be labelled.

The matrix does not name the edges. It says there are two edges between \(v_2\) and \(v_3\), but not which is \(e_1\). A graph rebuilt from its adjacency matrix is the same graph up to the names of the edges.

Loops

A loop at \(v_i\) is one edge whose set of endpoints is \(\{v_i\} = \{v_i, v_i\}\), so it adds 1 to the diagonal entry \(a_{ii}\). In the graph above the one loop \(e_5\) gives \(a_{44} = 1\). Two loops at a vertex give a 2 on the diagonal, and the \(1 \times 1\) matrix \([73]\) is a single vertex with 73 loops.

A loop adds 2 to the degree of its vertex (graphs) but only 1 to the matrix. So when there are loops, the row sum is not the degree.

Degree from the adjacency matrix. For each vertex \(v_i\), \[\deg(v_i) = (a_{i1} + a_{i2} + \cdots + a_{in}) + a_{ii},\] the sum of row \(i\) plus the diagonal entry of row \(i\).

Proof. Every edge with \(v_i\) as an endpoint is counted exactly once in row \(i\): an edge joining \(v_i\) to a different vertex \(v_j\) in \(a_{ij}\), and a loop at \(v_i\) in \(a_{ii}\). An edge joining \(v_i\) to a different vertex has one end at \(v_i\) and adds 1 to \(\deg(v_i)\), the same as it adds to the row. A loop has both of its ends at \(v_i\) and adds 2 to \(\deg(v_i)\), one more than it adds to the row. So the degree is the row sum plus one for each loop at \(v_i\), and there are \(a_{ii}\) loops at \(v_i\). \(\square\)

In the graph above:

Vertex Row sum Diagonal entry Degree
\(v_1\) \(0 + 1 + 0 + 1 = 2\) 0 2
\(v_2\) \(1 + 0 + 2 + 0 = 3\) 0 3
\(v_3\) \(0 + 2 + 0 + 0 = 2\) 0 2
\(v_4\) \(1 + 0 + 0 + 1 = 2\) 1 3

\(v_4\) meets \(e_4\) once and the loop \(e_5\) twice, so its degree is 3, not the row sum 2. For a graph without loops the diagonal is all 0 and the degree is just the row sum.

Counting the edges. Each edge is counted exactly once on or above the diagonal: an edge joining \(v_i\) and \(v_j\) with \(i < j\) in \(a_{ij}\), and a loop on the diagonal. So

\[\text{number of edges} = \sum_{i \le j} a_{ij},\]

the sum of the diagonal and everything above it. Above, that is \((0 + 1 + 0 + 1) + (0 + 2 + 0) + (0 + 0) + 1 = 5\). Adding up every entry counts each non-loop edge twice, once on each side of the diagonal, and each loop once, so adding the diagonal on top gives \(2e\). That is the degree formula summed over all the vertices, and it is the Handshake Theorem (graphs): above, \(9 + 1 = 10 = 2 \cdot 5\).

Reading a graph off a matrix

Given an adjacency matrix, the graph is drawn from the diagonal and the entries above it:

  1. Check it is an adjacency matrix: square, symmetric, non-negative integer entries (below).
  2. Draw a dot for each row and label it \(v_1, \dots, v_n\) in order.
  3. For each \(i < j\), draw \(a_{ij}\) edges between \(v_i\) and \(v_j\).
  4. For each \(i\), draw \(a_{ii}\) loops at \(v_i\).
  5. Ignore everything below the diagonal. It repeats what is above, and reading it too would draw every edge twice.

Then check: the number of edges drawn is the sum on and above the diagonal, and each degree in the drawing is its row sum plus its diagonal entry.

For example, take

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

It is square, symmetric and has non-negative integer entries. On and above the diagonal: \(a_{11} = 1\) is a loop at \(v_1\); \(a_{12} = 1\) is an edge \(v_1 v_2\); \(a_{23} = 2\) is two parallel edges \(v_2 v_3\); \(a_{24} = 1\) and \(a_{34} = 1\) are edges \(v_2 v_4\) and \(v_3 v_4\). Every other entry there is 0. That is 6 edges.

Figure 2: Reading a graph off an adjacency matrix. Only the diagonal and the entries above it, in blue, are used: each entry above the diagonal is a number of edges between two vertices, and each diagonal entry is a number of loops. The grey entries below the diagonal repeat the blue ones and are skipped. The blue entries add to 6, the number of edges. The degrees, in red, are row sum plus diagonal entry: v1 has row sum 2 and one loop, so degree 3.

The degrees are \(\deg(v_1) = 2 + 1 = 3\), \(\deg(v_2) = 4\), \(\deg(v_3) = 3\) and \(\deg(v_4) = 2\), adding to \(12 = 2 \cdot 6\). A larger example, with two loops and three parallel edges, is worked in 2026-10-27-matrix-representations-of-graphs.

Which matrices are adjacency matrices

A matrix is the adjacency matrix of some graph if and only if it is square (with at least one row), symmetric, and every entry is a non-negative integer \(0, 1, 2, \dots\)

Proof. (\(\Rightarrow\)) Shown under the definition: an adjacency matrix has a row and a column for each vertex, a graph has at least one vertex, every entry counts edges, and \(\{v_i, v_j\} = \{v_j, v_i\}\).

(\(\Leftarrow\)) Let \(M = [m_{ij}]\) be an \(n \times n\) symmetric matrix with \(n \ge 1\) and non-negative integer entries. Build a graph with vertices \(v_1, \dots, v_n\): for each \(i < j\) put \(m_{ij}\) edges between \(v_i\) and \(v_j\), and for each \(i\) put \(m_{ii}\) loops at \(v_i\). These are whole numbers of edges, at least 0, so this is a graph. The number of edges with endpoints \(\{v_i, v_j\}\) is then \(m_{ij}\) when \(i < j\), it is \(m_{ii}\) when \(i = j\), and when \(i > j\) it is \(m_{ji}\), which equals \(m_{ij}\) because \(M\) is symmetric. So \(M\) is this graph’s adjacency matrix. \(\square\)

So there are three things to check, and a matrix fails if any one of them fails:

Matrix Square Symmetric Entries in \(0, 1, 2, \dots\) Adjacency matrix?
\(\begin{bmatrix} 0 & 2 \\ 2 & 1 \end{bmatrix}\) yes yes yes yes: two parallel edges and a loop at \(v_2\)
\(\begin{bmatrix} 0 & 1 & 1 \end{bmatrix}\) no — yes no: one row, three columns
\(\begin{bmatrix} 0 & 1 \\ 0 & 0 \end{bmatrix}\) yes no yes no
\(\begin{bmatrix} 0 & \tfrac12 \\ \tfrac12 & 0 \end{bmatrix}\) yes yes no no: half an edge
\(\begin{bmatrix} 0 & 0 \\ 0 & 0 \end{bmatrix}\) yes yes yes yes: two isolated vertices, no edges

Nothing else is needed. The diagonal can hold any non-negative integer, and so can any entry off it. Four more are worked in 2026-10-27-matrix-representations-of-graphs.

Degrees and Euler circuits

The matrix holds everything needed to decide whether a graph has an Euler circuit (euler-circuits-and-trails): a connected graph has one exactly when every vertex has even degree.

  • The degrees are row sum plus diagonal entry, as above.
  • Connectedness can be read off too. The graph is not connected exactly when the vertices split into two non-empty groups with a 0 in every entry between a vertex of one group and a vertex of the other: then no edge crosses between the groups.

For \(M\) above the degrees are \(3, 4, 3, 2\). The graph is connected, since \(v_2\) is joined to every other vertex. Two vertices, \(v_1\) and \(v_3\), have odd degree, so there is no Euler circuit, but there is an Euler trail from \(v_1\) to \(v_3\). For the graph in the definition the odd vertices are \(v_2\) and \(v_4\), so it too has an Euler trail and no Euler circuit.

A degree must be computed with the diagonal added in before its parity is judged. A vertex with row sum 2 and one loop has degree 3, which is odd.

Common mistakes

  • Writing 2 on the diagonal for a loop. The adjacency matrix counts edges, and a loop is one edge, so it counts 1. The 2 for a loop belongs in the incidence matrix, which counts how many times a vertex meets an edge.
  • Taking the row sum as the degree when there are loops. Add the diagonal entry: \(\deg(v_i)\) is the row sum plus \(a_{ii}\).
  • Reading the whole matrix when drawing. Every entry off the diagonal appears twice. Read the diagonal and above only, or every edge comes out doubled.
  • Counting edges by adding all the entries. That counts each non-loop edge twice. Add the diagonal and the entries above it.
  • Expecting a zero diagonal and only 0s and 1s. That is true for simple graphs only. Loops put numbers on the diagonal, and parallel edges put numbers bigger than 1 off it.
  • Leaving off the labels. The matrix depends on the order of the vertices, so label the rows and columns.
  • Accepting a matrix that is not symmetric. \(a_{ij}\) and \(a_{ji}\) count the same edges and must be equal.

See also