Graphs: vocabulary, degrees and representations

A graph is the simplest mathematical model of a network: a collection of points, some pairs of which are joined. The points can be people and the joins friendships, or cities and roads, computers and cables, web pages and links, atoms and bonds, courses and prerequisites, or tasks that cannot run at the same time. Because the same mathematics applies to all of them, graph theory is one of the most widely used parts of discrete mathematics. Euler's solution of the Königsberg bridge problem in 1736, which we met in lesson 1, is usually taken as its starting point, and the subject has grown enormously since the middle of the twentieth century, driven by computing.

This lesson sets up the vocabulary, proves the first theorem of graph theory, the handshake lemma, introduces the families of graphs that appear throughout the rest of the course and shows how graphs are stored in a computer. Lessons 8 to 10 then study paths, trees and shortest routes.

Definitions

A simple graph \(G = (V, E)\) consists of a finite non-empty set \(V\) of vertices and a set \(E\) of edges, each edge being a set \(\{u, v\}\) of two different vertices. We write the edge \(\{u, v\}\) as \(uv\) for short; \(uv\) and \(vu\) are the same edge. If \(uv\) is an edge, the vertices \(u\) and \(v\) are adjacent, or neighbours, and the edge is incident with each of them. The number of vertices is usually written \(n = |V|\) and the number of edges \(m = |E|\).

Simple graphs have no loops (edges from a vertex to itself) and no multiple edges (two edges joining the same pair). Allowing these gives a multigraph, which is what Euler needed for Königsberg, where two bridges joined the same pair of land masses. A directed graph, or digraph, has edges with a direction, written as ordered pairs \((u, v)\) and drawn as arrows; one-way streets, web links and prerequisite relations are directed. Unless we say otherwise, graph means simple undirected graph.

A graph is an abstract object. Its drawing is only a picture: the positions of the vertices and the shapes of the edges carry no meaning, and edges that cross in a drawing do not meet at a vertex unless the crossing point is drawn as one. Two quite different-looking drawings can show the same graph.

Degrees and the handshake lemma

The degree \(\deg(v)\) of a vertex \(v\) is the number of edges incident with it, that is, the number of its neighbours in a simple graph. A vertex of degree 0 is isolated; a vertex of degree 1 is a leaf, a name that will make sense in lesson 9.

Theorem (handshake lemma). In every graph, the sum of the degrees equals twice the number of edges:

\[ \sum_{v \in V} \deg(v) = 2|E|. \]

Proof. Count the pairs \((v, e)\) where \(v\) is a vertex and \(e\) is an edge incident with \(v\). Counting by vertices, each vertex \(v\) appears in \(\deg(v)\) pairs, giving the left side. Counting by edges, each edge has exactly two endpoints and appears in two pairs, giving \(2|E|\). This is double counting, exactly as in the handshake problem of lesson 1; the name of the lemma comes from that problem, where the vertices are people and the edges are handshakes.

Corollary. Every graph has an even number of vertices of odd degree. Proof: the sum of all degrees is even. The vertices of even degree contribute an even amount, so the vertices of odd degree must also contribute an even amount, and a sum of odd numbers is even only when there is an even number of them.

The corollary already settles some questions. Is there a group of 9 people in which each person knows exactly 3 others? That would be a graph with 9 vertices all of odd degree 3, an odd number of odd-degree vertices, so no. Equivalently, the degree sum would be 27, which is not twice a whole number of edges.

Important families of graphs

Certain graphs appear so often that they have standard names.

• The complete graph \(K_n\) has \(n\) vertices with every pair adjacent. Each vertex has degree \(n - 1\), and there are \(\binom{n}{2}\) edges. \(K_3\) is a triangle.

• The path \(P_n\) has vertices \(v_1, \dots, v_n\) with edges \(v_1v_2, v_2v_3, \dots, v_{n-1}v_n\).

• The cycle \(C_n\), for \(n \ge 3\), is the path \(P_n\) with the extra edge \(v_nv_1\). Every vertex has degree 2.

• A graph is bipartite if its vertices can be split into two sets \(X\) and \(Y\) so that every edge has one end in each. The complete bipartite graph \(K_{m,n}\) has \(|X| = m\), \(|Y| = n\) and all \(mn\) edges between them.

• The hypercube \(Q_d\) has as vertices the \(2^d\) bit strings of length \(d\), with two strings adjacent when they differ in exactly one position. Every vertex has degree \(d\), so by the handshake lemma \(Q_d\) has \(d\,2^{d-1}\) edges. Hypercubes describe the wiring of some parallel computers and the structure of error-correcting codes.

A graph \(H\) is a subgraph of \(G\) if its vertices and edges are among those of \(G\). Subgraphs give a precise way to say that a network contains a triangle, a cycle of length 5, or a copy of \(K_4\). A useful fact about bipartite graphs, proved in lesson 8, is that a graph is bipartite exactly when it contains no cycle of odd length.

Degree sequences

The degree sequence of a graph lists its vertex degrees in decreasing order. \(K_4\) has degree sequence 3, 3, 3, 3; the path \(P_4\) has 2, 2, 1, 1. A natural question is which sequences of numbers can be degree sequences of simple graphs. The sum must be even, by the handshake lemma, and no degree can exceed \(n - 1\), but those conditions are not enough. The sequence 3, 3, 1, 1 has an even sum, yet no simple graph has it: two vertices of degree 3 in a 4-vertex graph would each be adjacent to all three others, so every vertex would have degree at least 2.

The Havel–Hakimi theorem, found independently by Václav Havel in 1955 and S. L. Hakimi in 1962, gives a complete test. A decreasing sequence \(d_1 \ge d_2 \ge \cdots \ge d_n\) is the degree sequence of a simple graph exactly when the sequence obtained by deleting \(d_1\) and subtracting 1 from each of the next \(d_1\) terms is, after re-sorting. Repeating the step either reaches all zeros, which is the degree sequence of a graph with no edges, or produces a negative number or a term too large, which shows the original sequence is impossible. The idea of the proof is that if a graph with the sequence exists, one with the vertex of largest degree joined to the vertices of the next largest degrees also exists, obtained by swapping edges.

When are two graphs the same?

Two graphs \(G\) and \(H\) are isomorphic if there is a bijection \(f\) from the vertices of \(G\) to the vertices of \(H\) such that \(uv\) is an edge of \(G\) exactly when \(f(u)f(v)\) is an edge of \(H\). Isomorphic graphs are the same graph with the vertices renamed. To show two graphs are isomorphic, give the bijection and check the edges. To show they are not, find an invariant, a property preserved by isomorphism, on which they differ: the number of vertices or edges, the degree sequence, the number of triangles, whether the graph is bipartite or connected, the length of the shortest cycle.

No simple, efficient test for isomorphism of general graphs is known, and finding one is a famous open problem. Trying all \(n!\) bijections works for very small graphs only. In 2015 László Babai announced an algorithm much faster than all earlier ones, though still slower than polynomial time; for the graphs met in practice, good programs decide isomorphism quickly.

Representing graphs in a computer

There are two standard ways to store a graph with vertices numbered \(0, 1, \dots, n - 1\).

The adjacency matrix is the \(n \times n\) matrix \(A\) with \(A_{ij} = 1\) if \(ij\) is an edge and 0 otherwise. For an undirected simple graph it is symmetric with zeros on the diagonal, and the sum of row \(i\) is \(\deg(i)\). It uses \(n^2\) entries whatever the number of edges, and testing whether two vertices are adjacent takes one lookup.

The adjacency list stores, for each vertex, a list of its neighbours. It uses space proportional to \(n + m\), which is far less than \(n^2\) for the sparse graphs common in practice: a road network has millions of intersections, but each meets only a few roads. Listing the neighbours of a vertex takes time proportional to its degree. Most graph algorithms, including those of lessons 8 to 10, use adjacency lists.

Counting walks with matrix powers

A walk of length \(k\) is a sequence of vertices \(v_0, v_1, \dots, v_k\) in which each consecutive pair is joined by an edge; vertices and edges may repeat. The adjacency matrix has a striking property: the entry \((A^k)_{ij}\) is the number of walks of length \(k\) from \(i\) to \(j\).

Proof by induction on \(k\). For \(k = 1\), \(A_{ij}\) is 1 exactly when there is a one-step walk from \(i\) to \(j\). Suppose the claim holds for \(k\). A walk of length \(k + 1\) from \(i\) to \(j\) consists of a walk of length \(k\) from \(i\) to some vertex \(l\), followed by an edge from \(l\) to \(j\). Summing over \(l\), the number of such walks is \(\sum_l (A^k)_{il} A_{lj}\), which is exactly the \((i, j)\) entry of \(A^k A = A^{k+1}\). Linear algebra and counting meet here: matrix multiplication is the sum rule and the product rule in disguise.

Since a closed walk of length 3 from a vertex back to itself is a triangle traversed in some direction, the diagonal of \(A^3\) counts triangles: each triangle contributes 2 to the diagonal entry of each of its three vertices, so the number of triangles is the trace of \(A^3\) divided by 6.

from itertools import permutations

n = 5
edges = [(0, 1), (0, 2), (1, 2), (1, 3), (3, 4)]

adj = {v: [] for v in range(n)}
A = [[0] * n for _ in range(n)]
for u, v in edges:
    adj[u].append(v); adj[v].append(u)
    A[u][v] = A[v][u] = 1
print("adjacency list:", adj)
degrees = [len(adj[v]) for v in range(n)]
print("degrees:", degrees, " sum =", sum(degrees), " 2|E| =", 2 * len(edges))

def mat_mult(X, Y):
    return [[sum(X[i][k] * Y[k][j] for k in range(n)) for j in range(n)] for i in range(n)]

A2 = mat_mult(A, A); A3 = mat_mult(A2, A)
print("walks of length 3 from 0 to 1:", A3[0][1])
print("triangles:", sum(A3[i][i] for i in range(n)) // 6)

def havel_hakimi(seq):
    seq = sorted(seq, reverse=True)
    while seq and seq[0] > 0:
        d = seq.pop(0)
        if d > len(seq):
            return False
        for i in range(d):
            seq[i] -= 1
            if seq[i] < 0:
                return False
        seq.sort(reverse=True)
    return True

for s in ([4, 3, 3, 2, 2, 2], [4, 4, 3, 1, 1, 1], [3, 3, 1, 1], [3, 3, 3, 3]):
    print(s, "graphic" if havel_hakimi(s) else "not graphic")

def isomorphic(e1, e2, n):
    E1 = {frozenset(e) for e in e1}; E2 = {frozenset(e) for e in e2}
    if len(E1) != len(E2):
        return False
    return any({frozenset((p[u], p[v])) for u, v in e1} == E2 for p in permutations(range(n)))

c5 = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)]
star = [(0, 2), (2, 4), (4, 1), (1, 3), (3, 0)]
print("C5 isomorphic to the pentagram:", isomorphic(c5, star, 5))

adjacency list: {0: [1, 2], 1: [0, 2, 3], 2: [0, 1], 3: [1, 4], 4: [3]}
degrees: [2, 3, 2, 2, 1]  sum = 10  2|E| = 10
walks of length 3 from 0 to 1: 4
triangles: 1
[4, 3, 3, 2, 2, 2] graphic
[4, 4, 3, 1, 1, 1] not graphic
[3, 3, 1, 1] not graphic
[3, 3, 3, 3] graphic
C5 isomorphic to the pentagram: True

The last check confirms a pleasant fact: the five-pointed star drawn by joining every second corner of a pentagon is isomorphic to the pentagon itself. Both are the cycle \(C_5\), drawn differently.