Representing a Graph by a Matrix
A graph can be recorded in several forms: as a list of vertices and edges, as a drawing, or as a matrix. The matrix form is useful because it turns the question “Are these two vertices adjacent?” into a question about a particular entry. But the matrix depends on an ordering of the vertices, so the ordering must always be stated. We will build matrices from explicit edge sets and see exactly what information they encode.
Throughout, graphs are finite and simple: they have no loops or multiple edges, and their edges are undirected. Write \(V(G)\) for the vertex set and \(E(G)\) for the edge set. If an edge joins vertices \(u\) and \(v\), write it as \(uv\). An ordering of the vertices is a list \(v_1,v_2,\dots,v_n\) in which each vertex appears exactly once, where \(n=|V(G)|\).
Each entry records whether one particular pair of vertices is joined by an edge. Because the graph is undirected, \(v_iv_j\in E(G)\) exactly when \(v_jv_i\in E(G)\), so \(a_{ij}=a_{ji}\). Thus the matrix is symmetric. Because the graph has no loops, no vertex is adjacent to itself, so \(a_{ii}=0\) for every \(i\). Its entries are all either zero or one because the graph is simple: there is either an edge between a pair or there is not.
When writing a matrix, state the vertex order before displaying it. Otherwise, a reader cannot tell which pair of vertices a particular entry refers to. In the examples below, the row and column order will be the displayed order of the vertex labels.
Encoding a Path, a Cycle and a Complete Graph
Worked Example: The Path \(P_4\)
Let \(G=P_4\) have vertex set \(V(G)=\{1,2,3,4\}\) and edge set \(E(G)=\{12,23,34\}\). Use the vertex order \(1,2,3,4\). To fill the matrix, examine each pair: \(12\), \(23\) and \(34\) are edges, while \(13\), \(14\) and \(24\) are not. Put a 1 in both positions for each edge, and put 0 in the diagonal positions and in positions for nonedges. This gives
Check: The 1-entries above the diagonal occur exactly in positions \((1,2)\), \((2,3)\) and \((3,4)\), which correspond to the three listed edges. Their matching entries below the diagonal occur in positions \((2,1)\), \((3,2)\) and \((4,3)\). All diagonal entries are 0. Thus the matrix records the edge set and is symmetric.
Worked Example: The Cycle \(C_4\)
Let \(G=C_4\) have vertex set \(V(G)=\{1,2,3,4\}\) and edge set \(E(G)=\{12,23,34,41\}\). Use the order \(1,2,3,4\). The four edges give 1-entries in the pairs of positions \(12,23,34,14\) and their reversed positions. The other distinct pair, \(13\), is not an edge, and all diagonal entries are 0. Therefore
Check: Reading the entries above the diagonal gives \(a_{12}=1\), \(a_{13}=0\), \(a_{14}=1\), \(a_{23}=1\), \(a_{24}=0\) and \(a_{34}=1\). These are precisely the six possible pairs on four vertices: the four edges \(12,14,23,34\) and the two nonedges \(13,24\). The matrix is symmetric, so the entries below the diagonal agree with these pair-by-pair checks.
Worked Example: The Complete Graph \(K_4\)
Let \(G=K_4\) have vertex set \(V(G)=\{1,2,3,4\}\) and edge set \(E(G)=\{12,13,14,23,24,34\}\). Use the order \(1,2,3,4\). Every pair of distinct vertices is an edge, so each off-diagonal entry is 1. No vertex is adjacent to itself, so each diagonal entry is 0:
Check: The entries above the diagonal are \(a_{12}=a_{13}=a_{14}=a_{23}=a_{24}=a_{34}=1\), matching all six edges in the edge set. There are no other distinct pairs of vertices, and the diagonal is 0. Hence the matrix represents exactly \(K_4\).
What the Matrix Records
Proof. First, take any simple graph on the fixed vertex set. Its adjacency matrix has entries in \(\{0,1\}\) by definition, has zero diagonal because there are no loops, and is symmetric because its edges are undirected. Thus every such graph gives a matrix of the stated form.
For the converse, take any symmetric \(n\)-by-\(n\) matrix with entries in \(\{0,1\}\) and zero diagonal. Define a graph on \(v_1,\dots,v_n\) by including the edge \(v_iv_j\) exactly when the matrix entry in position \((i,j)\) is 1. The zero diagonal ensures that no loop is included. Symmetry ensures that the rule gives an undirected edge consistently: the entries \((i,j)\) and \((j,i)\) agree, so the pair is either included once as an edge or not included. There are no multiple edges because each pair is either included or not. Finally, any graph giving the original matrix must contain exactly the pairs whose entries are 1, so it must be this same graph. This proves existence and uniqueness in both directions. \(\square\)
This result explains precisely what is encoded: with a fixed vertex order, no edge information is lost and no extra information is added. The graph is simple and undirected here; a matrix with nonzero diagonal or unequal entries in opposite positions does not represent such a graph under this definition.
Changing the Vertex Order
The same graph can have different-looking adjacency matrices if its vertices are listed in a different order. This is a change in the indexing, not a change in which vertices are adjacent. The rows and columns must be reordered together so that each row and column continues to refer to the same vertex.
Proof. By definition, \(b_{ij}=1\) exactly when \(w_iw_j\) is an edge, and \(b_{ij}=0\) otherwise. Since \(w_i=v_{\sigma(i)}\) and \(w_j=v_{\sigma(j)}\), this is exactly the condition that \(v_{\sigma(i)}v_{\sigma(j)}\) is an edge. By the definition of the original matrix, that condition is equivalent to \(a_{\sigma(i),\sigma(j)}=1\). If the pair is not an edge, both entries are 0. Hence \(b_{ij}=a_{\sigma(i),\sigma(j)}\) in every position. \(\square\)
Worked Example: Reordering the Vertices of a Path
Use the path \(G\) with \(V(G)=\{1,2,3,4\}\) and \(E(G)=\{12,23,34\}\). Its matrix in the order \(1,2,3,4\) was computed above. Now use the order \(1,3,2,4\). In that order, the consecutive pairs of indices correspond to vertex pairs \(13,32,24\); their edge status is, respectively, nonedge, edge, nonedge. Checking all distinct pairs, the edges are \(12\), \(23\) and \(34\), which now appear at index pairs \(13\), \(23\) and \(24\), respectively. Therefore the matrix is
Check: The 1-entries above the diagonal occur at \(13,23,24\). Under the order \(1,3,2,4\), those index pairs mean the vertex pairs \(12,32,34\), all of which are edges. The other three distinct index pairs mean \(13,14,24\), none of which is an edge. The matrix remains symmetric with zero diagonal. It differs from the first matrix, but it describes the same graph because only the order changed.
Reading the Representation Carefully
For a graph whose vertices are already labeled, fixing their order gives one exact adjacency matrix. If the labels are discarded, different orders can produce different matrices for the same underlying graph. Thus it is important to distinguish a graph with a specified labeling and order from an unlabeled graph considered up to relabeling. The proposition describes how the matrices are related when the order changes.
A common mistake is to reorder only the rows. For example, begin with the matrix of \(P_4\) in order \(1,2,3,4\), and swap the first two rows without swapping the corresponding columns. The first two rows become \((1,0,1,0)\) and \((0,1,0,0)\), while the first two columns still refer to vertices \(1\) and \(2\). The resulting array is not symmetric: its entry in position \((1,2)\) is 0, while its entry in position \((2,1)\) is 1. It therefore cannot be the adjacency matrix of an undirected simple graph under the stated convention. The correction is to perform the same swap on columns as on rows, so that both indices continue to use the same vertex order.
Also, do not put a 1 on the diagonal for a vertex that has an edge to another vertex: an edge \(uv\) is recorded in the two off-diagonal positions for the pair \(u,v\). A diagonal 1 would record a loop, which is excluded from simple graphs. In a directed graph, the two opposite entries need not agree, but directed graphs are outside the convention used here.
Adjacency matrices give a compact, exact encoding, particularly when a graph has a small vertex set. The essential discipline is to declare the order first, fill both positions for each undirected edge, and check that every diagonal entry is 0 and every pair of opposite entries agrees. Questions about extracting vertex degrees and neighborhoods from these matrices will use this representation further.
Check Your Understanding
For each question, state the vertex order whenever you write a matrix.
- Let \(V(G)=\{a,b,c\}\) and \(E(G)=\{ab,ac\}\). Write the adjacency matrix in the order \(a,b,c\), and check its diagonal and symmetry.
- Write the adjacency matrix of the graph on \(\{1,2,3,4\}\) with edge set \(\{12,23,34,14\}\), using the order \(1,2,3,4\).
- For an \(n\)-vertex simple graph, explain why its adjacency matrix has exactly \(n\) diagonal entries and why each is 0.
- Suppose a symmetric zero-one matrix has zero diagonal. Describe how to construct a simple graph from it, and explain why the resulting graph is unique for the fixed vertex order.
- Explain why changing the vertex order requires reordering both rows and columns, not just one of them.