Motivation
A drawing does not determine a graph by the positions or lengths of its lines. What matters is which vertices are joined. To compare two drawings we need a precise notion of relabeling; to perform a computation we must also choose how to store the adjacency information. A representation records a particular labeling, whereas an isomorphism identifies graphs that differ only by their names.
Definitions and storage
Definition 8.1.1
(Adjacency matrix and adjacency list)
Throughout, is a finite simple undirected graph: each edge is a two-element subset of , so loops and repeated edges are excluded. Write and . Choose an ordering . The adjacency matrix has if and otherwise. It is symmetric with zero diagonal. Conversely, each symmetric zero-diagonal zero–one matrix determines exactly one simple graph on its ordered vertex set.
An adjacency list records, for each vertex, its neighbors. Each edge occurs in two lists, and an isolated vertex has an empty list; the vertex set must still be recorded so that isolated vertices are not lost.
A matrix takes entries and answers an adjacency query with one indexed lookup. Lists occupy entries and permit a full neighbor scan of in operations including access to its list, but testing whether an arbitrary pair is adjacent may require scanning a list. These bounds assume indexed vertices and ordinary constant-time array access; ordering or hashing the lists can change the trade-off.
What the encoding does and does not store
Suppose a data file gives only the edge pairs and . It does not say whether the intended vertex set is , or whether there is also an isolated vertex . These give nonisomorphic graphs. A complete encoding must specify the vertices as well as the edges. When the vertices have already been numbered , a list of those numbers or the integer supplies the missing information. Repeating an edge in a purported simple-graph edge list does not create another edge; a program must either reject a duplicate or explicitly treat the input as a set. The results below assume a valid encoding of a simple graph.
The matrix makes the distinction particularly visible. The isolated vertex adds an entire zero row and zero column. The number of ones in row equals , while the sum of all entries is : each edge produces one entry in each of two symmetric positions. Hence one can reconstruct the edge set by examining only positions above the diagonal. This does not mean that the matrix itself is independent of ordering. A new ordering changes which row describes which vertex, even though the underlying graph is unchanged.
Worked example 8.1.2
(An isolated vertex is part of the graph)
Let have vertex set and edges . In that order its matrix is
The row sums are and sum to . The fourth row identifies vertex as isolated. If the vertex set were instead , the same two edge pairs would describe a three-vertex path; its matrix would be the upper-left block. The graphs are not isomorphic because a bijection between vertex sets of different sizes cannot exist.
Subgraphs: choosing vertices and choosing edges
Before comparing two whole graphs, it helps to distinguish two ways of looking at part of a graph.
Definition 8.1.3
(Subgraph, spanning subgraph and induced subgraph)
A subgraph of is a graph with and
where denotes the set of two-element subsets of . Thus every retained edge must have both endpoints in , but we may omit edges even when both endpoints remain. A subgraph is spanning when : it retains every vertex, including any that become isolated. The induced subgraph on , written , retains every original edge with both endpoints in :
Once is chosen, its induced subgraph is fixed; an ordinary subgraph on can have fewer edges. Deleting a vertex removes that vertex and all its incident edges, giving . Deleting an edge removes only that edge and retains all vertices. These are different operations, even if a drawing omits the isolated vertices they leave behind.
For the adjacency matrix, forming means keeping exactly the rows and columns indexed by , in the same relative order. The resulting matrix is a principal submatrix. Forming an arbitrary subgraph on may additionally require changing some symmetric pairs of ones to zeroes. Changing a row without its matching column does not delete a graph vertex.
Worked example 8.1.4
(A path can be a subgraph without being induced)
Let have vertices and edges . On the graph is a triangle, because all three edges are retained. The graph with vertex set and only edges is a subgraph, but is not the induced subgraph on . The graph with all four original vertices and edges is instead a spanning subgraph; vertex remains present and isolated. Finally, deleting vertex from leaves vertices and just edge , not the path with edges .
This distinction matters when transferring properties. Every subgraph of an acyclic graph is acyclic, since a cycle in the subgraph would already be a cycle in the original graph. Every subgraph of a bipartite graph is bipartite: intersect its two independent sides with the retained vertex set, and observe that deleting edges cannot introduce an edge within either side. Connectedness behaves differently. In the path , the induced subgraph on has two isolated vertices. A path between retained vertices can require a vertex that has been deleted.
Shortest paths have no shortcuts between their own vertices
Definition 8.1.5
(Induced path and chord)
A path has distinct vertices and edges . It is an induced path if these are all the edges of . An additional edge with is called a chord of the path.
Merely being a path does not rule out chords in the surrounding graph: the two-edge path in the triangle above is an example.
Theorem 8.1.6
(An unweighted shortest path is induced)
Let be vertices joined by a path in a finite simple graph. Every path from to having the fewest edges is induced. The converse need not hold.
Proof
(A chord would shorten the path)
Let be shortest. A chord with would replace the segment by a single edge. The resulting sequence is still a path: it uses a subsequence of the original distinct vertices. Its length is , a contradiction. Thus no chord exists. This also covers lengths zero and one, when there is no possible chord.
Proof X-ray
What a shortest-path argument is allowed to change
The endpoints remain fixed, and the only objective is the number of edges. A chord saves at least one edge while preserving the endpoints. A shorter route through vertices outside the path is a different possibility; the definition of an induced path says nothing about such vertices. The proof therefore gives one implication, rather than an equivalence. It also does not apply unchanged to a weighted path problem: a chord might have greater weight than the segment it replaces.
Worked example 8.1.7
(Induced does not mean shortest)
Take the five-cycle with edges . The path is induced: among its four vertices the only edges are . Yet it is not a shortest path from to , because has two edges instead of three. The shortcut uses vertex , which the induced-subgraph test never examines. By contrast, in a triangle a two-edge route already fails the induced-path test because its endpoints are adjacent.
Isomorphism preserves edges and nonedges
Definition 8.1.8
(Isomorphism and automorphism)
An isomorphism from to is a bijection such that, for every pair of distinct vertices ,
Both directions matter: edges and nonedges are preserved. An automorphism is an isomorphism from a graph to itself. The empty graph is isomorphic to itself by the empty bijection; it is not isomorphic to a graph with a vertex.
Relabeling as a matrix identity
Theorem 8.1.9
(Permutation matrices describe isomorphism)
Let and have ordered vertex sets and , with adjacency matrices and . They are isomorphic if and only if a permutation matrix satisfies .
Proof
(Computing the entries of )
To see the convention, let column of be the standard basis vector . Then . Thus the displayed equality says that preserves adjacency and nonadjacency. Conversely any isomorphism from to defines such a permutation. The inverse of an isomorphism is also an isomorphism, so this proves the stated equivalence. In particular, changing the order of one graph's vertices changes its matrix by simultaneous row and column permutations, not by an arbitrary independent permutation of rows and columns.
Definition 8.1.10
(Isomorphism invariant)
A property preserved by every isomorphism is an invariant. Different invariant values prove nonisomorphism. Equal values only mean that this particular test has not separated the graphs. To prove isomorphism, give a bijection and check the adjacency equivalence; do not merely list matching invariants.
For example, an isomorphism maps each vertex's neighbors bijectively to the neighbors of its image. Hence degrees, the sorted degree sequence, vertex and edge counts, and the number and sizes of connected components are preserved. A path maps to a path, which justifies the component claim; its inverse ensures components correspond bijectively.
Counterexample mode
A degree sequence does not determine a graph
The six-cycle and the disjoint union both have six vertices, six edges and degree sequence . Yet is connected and the two triangles are not, so no isomorphism exists. A drawing can suggest this distinction, but connectedness gives a proof independent of the drawing.
Checking a proposed correspondence
An isomorphism is a useful certificate because a reader can check it directly. First check that the proposed images are all in the target vertex set and that each target appears exactly once. Then examine every unordered pair of distinct source vertices: compare its adjacency bit with that of its image. If all agree, the definition holds. If one disagrees, that pair is a short, explicit reason the proposed map fails. With two adjacency matrices, checking a supplied map this way takes pair comparisons after checking the bijection; storage for the map and its inverse is beyond the input. This is the cost of verification, not a bound for finding a suitable map. Testing all possible bijections is a finite decision method, but this observation alone gives no efficient general algorithm.
If both graphs are supplied as valid edge lists, there is another check. Verify bijectivity, map every source edge, and compare the resulting set with the target edge set. Equality ensures preservation of both edges and nonedges: a target edge not in the image, or a mapped pair absent from the target, shows failure. With a bijection, distinct source edges have distinct images. If the source and target edge counts are already known to agree, checking that every mapped source edge is a target edge is enough, because an injective map between finite edge sets of the same size is then surjective. Without the equality of edge counts this shortcut is invalid. The time depends on how membership in the target edge set is implemented; one cannot promise constant-time membership merely because an adjacency list exists.
Worked example 8.1.11
(An edge-preserving bijection can still fail)
Let have vertices and edges , and let have vertices and edges . The bijection , , sends each edge of to an edge of , but it sends the nonedge to the edge . Thus it is not an isomorphism. Indeed the graphs have two and three edges respectively, so no other bijection can be an isomorphism either. This example explains why the definition uses an equivalence rather than only the forward implication.
The choice of drawing cannot repair a failed certificate. If a crossing point is not listed as a vertex, it is not automatically a vertex; conversely, drawing two vertices close together does not make them adjacent. Every claimed correspondence must be checked against the given vertex and edge sets, not against visual similarity. A connected graph drawn in a complicated way and the same graph drawn without crossings still have identical adjacency data under the identity map.
Complements: recording exactly the missing edges
Definition 8.1.12
(Complement)
The complement of a simple graph has the same vertex set and edge set . For each pair of distinct vertices, exactly one of and contains that edge. No loop is introduced.
Consequently, if is the adjacency matrix of in a fixed ordering, then
where is the all-one matrix and is the identity matrix. Off the diagonal this replaces each zero by one and each one by zero; on the diagonal . Using alone would introduce a loop at every vertex. Also, complementing twice returns , and because the possible neighbors of split between the two graphs.
A bijection is an isomorphism from to if and only if the same bijection is an isomorphism from to . Indeed, for distinct , being adjacent in the complements means precisely being nonadjacent in the original graphs, and the original adjacency equivalence can be negated in both directions. Complementing again proves the reverse assertion. Likewise, taking an induced subgraph commutes with complementation:
Both sides have vertex set , and a distinct pair from is an edge on either side exactly when it is absent from . The complement on the left is taken on , not on the larger set .
Theorem 8.1.13
(Disconnectedness forces a connected complement)
If a finite simple graph has vertices and is disconnected, then every two distinct vertices of are joined by a path of length at most two. In particular, is connected.
Proof
(Different components or a common one)
If lie in different components of , they are not adjacent in , so they are adjacent in . If they lie in the same component, choose a vertex in another component, which exists because is disconnected. Neither nor is an edge of , so is a path in . The three vertices are distinct. These two cases exhaust the pairs.
Thus at least one of and is connected when . The theorem does not say that exactly one is connected. It is a statement about the original graph being disconnected; its logically equivalent contrapositive says that a disconnected complement forces the original graph to be connected.
Counterexample mode
Both a graph and its complement can be connected
For the four-vertex path with edges , the complement has edges . Those edges form the path , so both graphs are connected. The map , , , even gives an isomorphism from the original path to its complement: the three original edges map to exactly . This does not mean that complementation preserves connectedness in general. A complete graph on at least two vertices is connected, while its complement has no edges.
Practice on restrictions and complements
Quick check
(In the graph with vertices and edges , determine whether the path is induced and whether it is shortest between its endpoints. Compare it with .)
Solution · Answer
On the edges are exactly , so the first path is induced. Edge is absent, so a one-edge route cannot exist; the given two-edge path is shortest. The second path is a valid path but has chord , and replacing by shortens it. It is neither induced nor shortest.
Quick check
(Let consist of a triangle on and the isolated vertex . Find . Explain both its connectedness and why its longest distance is exactly two.)
Solution · Answer
The missing pairs are , so the complement is a star centered at . Each leaf is adjacent to the center, and any two distinct leaves are joined through it. They are not adjacent to one another, so their distance is exactly two. This also shows that the length-two bound in the theorem cannot generally be replaced by one. A disconnected edgeless , by contrast, has a complete complement, where distinct vertices have distance one.
Quick check
(Prove that restricting an isomorphism to a set gives an isomorphism . Why is the word “induced” essential?)
Solution · Answer
The restriction is a bijection from onto . A pair in is an edge of exactly when it is an edge of , exactly when its image is an edge of , and exactly when that image pair is an edge of . Thus both edges and nonedges are preserved. For arbitrary independently chosen subgraphs the conclusion fails: even the identity isomorphism of a triangle need not map a two-edge spanning path isomorphically to the whole triangle. Induced restriction retains all the original pair information, so the original equivalence remains available.
Matrix powers count walks
Theorem 8.1.14
(A walk count encoded by a matrix power)
For every integer , is the number of walks of length from to . Vertices and edges may repeat. Here , so the length-zero walk stays at its starting vertex.
Proof
(Induction on the walk length)
For the identity matrix gives exactly those walks, and for the claim is the definition of adjacency. If it holds for , matrix multiplication gives . Each summand counts walks whose penultimate vertex is : append the edge to a length- walk when that edge exists. These classes are disjoint and exhaust all length- walks. Induction proves the formula. For there are no indices to check.
For example, counts common neighbors when , and . The latter counts a walk out and back, even though a simple graph has no loops. A positive matrix entry detects a walk of the specified length, not necessarily a simple path of that length.
Worked examples
Worked example 8.1.15
(Exhibit a relabeling)
Let have vertex set and edges , and let have vertex set and edges . The map , , , sends those five edges respectively to . The map is bijective. Since exactly five edges are listed in each graph, the five distinct images exhaust ; therefore nonedges are preserved as well and the map is an isomorphism.
Worked example 8.1.16
(Read a square from its matrix)
For the path , let . Then . The entry counts and , while counts . The first two walks repeat a vertex; none is a cycle under the usual simple-cycle convention.
Relabeling and walk counts
Let and satisfy for a permutation matrix. Since , repeated multiplication gives for every . This identity can also be seen directly: relabel every vertex in a walk, preserving its successive edges and its length, and use the inverse relabeling to reverse the construction. In particular, corresponding vertices have the same number of closed walks of every fixed length, and summing the diagonal entries shows . These quantities can therefore disprove an alleged isomorphism. They are still invariants, and a collection of matching invariants is not by itself a proposed bijection.
There is a useful special case for triangles. In a simple graph a closed walk of length three has three distinct vertices: a repeated adjacent vertex would require a loop, and returning to the start after two steps would leave a forbidden loop as the third step. Consequently every such walk traverses a triangle, and each triangle contributes six walks in total, one from each of its three vertices in either direction. Thus counts triangles. This division relies on the simple undirected convention. It would require a fresh argument if loops or parallel edges were permitted.
Common mistakes
Common mistake
(Reading a zero diagonal as “no edges”)
A zero diagonal says there are no loops; it does not say there are no edges, because an edge is recorded off the diagonal.
Common mistake
(Reading any zero–one matrix as an undirected graph)
A symmetric zero-diagonal matrix of zeroes and ones represents an undirected simple graph, but a nonsymmetric such matrix represents directed adjacency only after a separate convention has been chosen.
Common mistake
(Permuting rows without permuting columns)
Swapping two rows without swapping the corresponding columns can destroy symmetry and is not the matrix operation for renaming vertices. A change of labels must act on the name at both ends of each edge.
Exercises
Quick check
(A graph on vertices has edges . Write its adjacency matrix in that order and its adjacency lists, including every vertex. Give a bijection to the path .)
Solution · Answer
The rows are , , , . The lists are , , , . The bijection , , , maps the three listed edges to exactly the three target edges, and hence also preserves nonedges.
Quick check
(Are a six-cycle and two disjoint triangles isomorphic? Explain why equal degrees do not suffice and give a decisive invariant.)
Solution · Answer
No. Both graphs have all degrees two, but the first has one connected component and the second has two. An isomorphism must preserve components, so matching degree sequences do not suffice.
Quick check
(For a simple graph, prove that the diagonal entry is twice the number of triangles containing . Why does this not say that all length-three walks are triangles?)
Solution · Answer
A closed length-three walk based at has form . Since the graph is simple, adjacent vertices differ and the closing edge forces ; also . Thus the three vertices are distinct and form a triangle. Each triangle containing gives exactly two such walks, one in each direction. The matrix-power theorem counts them. A non-closed length-three walk can backtrack, for instance on a single edge, and is not a triangle.