Degrees, Representations, and Isomorphism

The question

Two engineers sketch the same data-center network. One draws eight servers at the corners of a cube. The other draws them around a circle, links each to its two neighbors on the circle, and adds four long links across.

In the first sketch two corners are linked when their names differ in one bit. Is it the same network, with the servers renamed? Both sketches have 8 servers and 12 links, and every server has 3 links. That is evidence, not proof. This module makes "the same graph" precise, gives a short certificate when two graphs are the same, and gives short certificates when they are not.

The naive approach, and where it wastes work

Two graphs on the same vertex count are the same up to renaming when some bijection between their vertices carries links to links and non-links to non-links. The obvious search tries every bijection:

from itertools import permutations

def network(edges):
    g = {}
    for u, v in edges:
        g.setdefault(u, set()).add(v)
        g.setdefault(v, set()).add(u)
    return g

def same_up_to_renaming(g, h):
    V, W = sorted(g), sorted(h)
    if len(V) != len(W):
        return None
    for image in permutations(W):
        f = dict(zip(V, image))
        if all((v in g[u]) == (f[v] in h[f[u]]) for u in V for v in V if u != v):
            return f
    return None

cube = network([(x, x ^ (1 << i)) for x in range(8) for i in range(3) if x < x ^ (1 << i)])
ring = network([("abcdefgh"[i], "abcdefgh"[(i + 1) % 8]) for i in range(8)]
               + [("a", "d"), ("b", "g"), ("c", "f"), ("e", "h")])
f = same_up_to_renaming(cube, ring)
assert f is not None and all(f[y] in ring[f[x]] for x in cube for y in cube[x])

For 8 servers that is up to $8! = 40, 320$ bijections; for 20 it is more than $2 \times 10^{18}$ . When the answer is "no", the search has to try every one of them, and its "no" is believable only if you rerun it. We want short evidence both ways.

Graphs as data

In this course a graph is simple unless we say otherwise: no loops and no two edges joining the same pair of vertices. Two vertices joined by an edge are adjacent, or neighbors. The degree $d (v)$ is the number of neighbors of $v$ ; $Δ (G)$ and $δ (G)$ are the largest and smallest degrees, and $G$ is $k$ -regular if every degree is $k$ . Listing the degrees from largest to smallest gives the degree sequence. Module 3 proves the degree-sum formula: the degrees add up to twice the number of edges.

A program can store a graph in two common ways:

Adjacency lists: for each vertex, the set of its neighbors (the network function above). Memory $O (n + m)$ for $n$ vertices and $m$ edges, and listing the neighbors of $v$ costs $d (v)$ .
Adjacency matrix: an $n \times n$ table with a 1 in row $u$ , column $v$ when $u v$ is an edge. Memory $n^{2}$ , but "is $u v$ an edge?" is a single lookup. The matrix of a simple graph is symmetric with zeros on the diagonal, and row $v$ adds up to $d (v)$ .

Neither is the graph itself. The same graph has many matrices, one for each order of its vertices, and that is exactly the renaming problem again.

Isomorphism

Definition. An isomorphism from $G$ to $H$ is a bijection $f : V (G) \to V (H)$ such that $u v$ is an edge of $G$ if and only if $f (u) f (v)$ is an edge of $H$ . If one exists, $G$ and $H$ are isomorphic, written $G ≅ H$ .

Both directions matter. A bijection that only sends edges to edges can still miss edges of $H$ : it is an isomorphism only if it also sends non-edges to non-edges.

An isomorphism is a certificate: given $f$ , checking it takes one pass over the edges of $G$ and a count. If $G$ and $H$ have the same number of edges and a bijection $f$ sends every edge of $G$ to an edge of $H$ , then $f$ sends non-edges to non-edges too: the edge map $u v \mapsto f (u) f (v)$ is one to one, so it hits $e (G) = e (H)$ edges, which is all of them, and a non-edge $u v$ cannot land on an edge $f (x) f (y)$ , because $f$ is one to one and $x y$ is the only pair that lands there.

For the two sketches, one isomorphism reads the cube's corners as 3-bit strings and walks them around the ring in the order 000, 001, 011, 010, 110, 111, 101, 100, where consecutive strings differ in one bit:

order = [0b000, 0b001, 0b011, 0b010, 0b110, 0b111, 0b101, 0b100]
f = {x: "abcdefgh"[i] for i, x in enumerate(order)}
assert all(f[y] in ring[f[x]] for x in cube for y in cube[x])
assert sum(map(len, cube.values())) == sum(map(len, ring.values()))

So the answer to the opening question is yes.

Invariants: certificates for "no"

A property is an invariant if isomorphic graphs always share it.

Proposition (isomorphism invariants)

If $G ≅ H$ , then $G$ and $H$ have the same number of vertices, the same number of edges, the same degree sequence, and, for every $k \geq 3$ , the same number of cycles of length $k$ .

Proof. Let $f$ be an isomorphism. It is a bijection, so the vertex counts agree.

Edges. Define $F (u v) = f (u) f (v)$ for each edge $u v$ of $G$ . By the definition, $F (u v)$ is an edge of $H$ . It is one to one, because $f$ is: different pairs of vertices go to different pairs. It is onto: an edge $x y$ of $H$ is $f (u) f (v)$ for $u = f^{- 1} (x)$ and $v = f^{- 1} (y)$ , and then $u v$ is an edge of $G$ by the "if" direction. So $F$ is a bijection between the edge sets.

Degrees. The same argument, restricted to the edges at $v$ , shows that $f$ maps the neighbors of $v$ one to one onto the neighbors of $f (v)$ . So $d (f (v)) = d (v)$ for every $v$ , and since $f$ is a bijection on vertices, the two degree sequences are the same list.

Cycles. A cycle of length $k$ is a list of $k$ distinct vertices $v_{1}, \dots, v_{k}$ with each consecutive pair adjacent and $v_{k} v_{1}$ adjacent, read up to the starting point and direction. Applying $f$ gives $k$ distinct vertices of $H$ with the same adjacencies, so a cycle of length $k$ ; distinct cycles go to distinct cycles because $f$ is one to one; and $f^{- 1}$ , also an isomorphism, carries cycles of $H$ back. So the cycles of length $k$ correspond one to one. $◻$

Proof moves used here.

Bijection: to show two counts are equal, build a map between the two sets and check it is one to one and onto. The "only if" half of the definition sends edges to edges; the "if" half is what makes the edge map onto.
Invariant: a property every isomorphism preserves can only ever certify "not isomorphic".

The proposition only works one way. A difference in any invariant proves two graphs are not isomorphic. Agreement on every invariant you check proves nothing.

Two pairs that agree on the easy invariants:

The 6-cycle $C_{6}$ and two disjoint triangles: both 2-regular with 6 vertices and 6 edges. The second has 2 triangles and the first has none, so they are not isomorphic.
The cube and the Wagner graph: take the ring of the opening sketch but join each server to the one diametrically opposite ( $a$ – $e$ , $b$ – $f$ , $c$ – $g$ , $d$ – $h$ ) instead. Both are 3-regular with 8 vertices and 12 edges, and neither has a triangle. They are still not isomorphic; the lab asks you to find an invariant that proves it.

Predict: two graphs have the same degree sequence and the same number of triangles. Must they be isomorphic?

No. The proposition gives certificates for "no" only. Agreeing on a list of invariants leaves the question open: you either find an isomorphism or a further invariant that differs.

Refining by degree

A search can use invariants to prune. Color every vertex by its degree. Then recolor each vertex by its old color together with the multiset of its neighbors' colors, and repeat until the number of colors stops growing. This is color refinement. To compare two graphs, run it on both together, so that the colors mean the same thing on each side.

Lemma. If $f$ is an isomorphism from $G$ to $H$ , then after every round of refinement (run on both together), $v$ and $f (v)$ have the same color.

Proof. By induction on the round. Before the first round, colors are degrees, and $f$ preserves degree. Suppose $v$ and $f (v)$ agree for every $v$ after round $r$ . The neighbors of $f (v)$ are exactly the images of the neighbors of $v$ , so by the hypothesis their multisets of round- $r$ colors are equal; together with the equal old colors, the round- $(r + 1)$ colors agree. $◻$

So any difference in the final color counts is a certificate that $G ≇ H$ , and an isomorphism search only needs to try mapping a vertex to vertices of the same final color.

Predict: what does refinement do on a 3-regular graph?

Nothing. Every vertex starts with color 3, and every vertex sees three neighbors of color 3, so the colors never split. On the cube and the Wagner graph refinement gives identical colors: it cannot tell them apart, though another invariant can.

Two families worth knowing

The $n$ -dimensional cube $Q_{n}$ . For $n \geq 1$ , its vertices are the $2^{n}$ strings of $n$ bits, and two strings are adjacent when they differ in exactly one position. The cube sketch is $Q_{3}$ .

Proposition. For every $n \geq 1$ , $Q_{n}$ is $n$ -regular, has $n 2^{n - 1}$ edges, and is bipartite.

Proof. A string has exactly $n$ neighbors, one for each position that can be flipped. Each edge has two ends, so the degrees add up to twice the number of edges: $2 m = n 2^{n}$ .

Recall that a graph is bipartite if its vertices split into two parts with every edge joining the two parts. Color a string by the parity of its number of ones (its weight). Flipping one bit changes the weight by 1, so every edge joins an even-weight string to an odd-weight one: the two parities are the two parts. $◻$

The Petersen graph. Its vertices are the 10 two-element subsets of ${1, 2, 3, 4, 5}$ , and two subsets are adjacent when they are disjoint. For example ${1, 2}$ is adjacent to ${3, 4}$ , ${3, 5}$ and ${4, 5}$ .

Proposition. The Petersen graph is 3-regular with 15 edges, and it has no cycle of length 3 or 4.

Proof. A pair $A$ is disjoint from exactly the pairs inside the other three elements, and there are $(\binom{32}{=}) 3$ of them; so the graph is 3-regular and has $3 \cdot 10 / 2 = 15$ edges.

No triangle: three pairwise disjoint pairs would need 6 different elements.

No 4-cycle: suppose $A, B, C, D$ is a 4-cycle. Then $A$ and $C$ are not adjacent (that would make the triangle $A, B, C$ ), so they are distinct pairs that intersect, and $A \cup C$ has exactly 3 elements. Both $B$ and $D$ are disjoint from $A \cup C$ , so both lie inside the remaining 2 elements, and $B = D$ . That contradicts the four vertices being distinct. $◻$

Proof moves used here. Double counting: the ends of the edges of $Q_{n}$ , counted by vertex and by edge, give its edge count. Parity: the weight of a string changes parity along every edge of $Q_{n}$ . Pigeonhole: three pairwise disjoint pairs cannot fit in five elements. Contradiction: a 4-cycle would force two of its vertices to be equal.

What a certificate costs

An isomorphism is checked in $O (n + m)$ . A differing invariant is checked by computing it twice: degree sequences in $O (n + m)$ , triangles in $O (n \cdot Δ^{2})$ with adjacency sets (which answer "is $u v$ an edge?" in constant time), and 4-cycles with more work still. The naive search costs up to $n!$ bijections. No known method decides isomorphism in polynomial time for all graphs, but refinement and pruning make the search fast on almost every graph you will meet.

A problem that looks different

Two chemists draw the same molecule from different angles and number the atoms differently. A database must recognize that the drawings agree, and must explain why two drawings that look alike do not. Nothing in the question says "graph". The lab's last exercise is another question of this kind.

Practise

The lab runs in your browser. Your code searches for an isomorphism, extending a partial renaming one vertex at a time and drawing each step, and computes invariants that prove two graphs differ. Half of the lab is proofs: assemble a proof that isomorphisms preserve distance, find the false step in an argument about color refinement, and write a proof for a problem that names no technique.

Recap

You can now: store a graph as adjacency lists or a matrix; define isomorphism with both directions; prove that order, size, degree sequence and cycle counts are invariants; prove that refinement colors are invariants; and prove the basic facts about $Q_{n}$ and the Petersen graph.
Invariant: an isomorphism maps neighbors onto neighbors, so everything defined from adjacency alone is preserved.
Complexity achieved: an isomorphism is checked in $O (n + m)$ , and an invariant such as the degree sequence or the triangle count in polynomial time, against up to $n!$ bijections for the naive search.
Failure mode: treating agreement on a few invariants as proof of isomorphism; and checking only that edges go to edges.
In real software: NetworkX's is_isomorphic runs the VF2 search, which extends a partial mapping and prunes it, and weisfeiler_lehman_graph_hash computes a color-refinement fingerprint.
Next: module 3 proves the degree-sum formula and characterizes bipartite graphs by odd cycles.

Check yourself

After the lab, the tutor will ask you to defend your work out loud:

Where does the proof that isomorphisms preserve edge counts use the "if" half of the definition?
Why can refinement prove two graphs are different but never prove they are the same?
In the proof that the Petersen graph has no 4-cycle, where is "no triangle" used?

Topic list modeled on the public syllabus of UIUC Math 412 (Graph Theory), which follows D. B. West, Introduction to Graph Theory, 2nd ed., Chapters 1–7. All lessons, proofs, examples, code and exercises here are original. This course is independent and not affiliated with or endorsed by the University of Illinois.

Degrees, Representations, and Isomorphism

The question

The naive approach, and where it wastes work

Graphs as data

Isomorphism

Invariants: certificates for "no"

Refining by degree

Two families worth knowing

What a certificate costs

A problem that looks different

Practise

Recap

Check yourself

Now try it yourself