Theory Notebook

Converted from theory.ipynb for web reading.

§11.01 Graph Basics — Theory Notebook

Companion to notes.md. Every definition, theorem, and AI connection from the notes is demonstrated with executable Python.

Sections

Graph objects and adjacency matrices
Degree, handshaking lemma, and degree sequences
Walks, trails, paths, and cycles
Connectivity and components
Special graph families
Trees and spanning trees
Bipartite graphs
Planar graphs and Euler's formula
Graph isomorphism and the WL test
Graph coloring and chromatic polynomial
Graph motifs and triangle counting
Directed graphs and DAGs

Code cell 2

import numpy as np
import matplotlib.pyplot as plt
import matplotlib as mpl

try:
    import seaborn as sns
    sns.set_theme(style="whitegrid", palette="colorblind")
    HAS_SNS = True
except ImportError:
    plt.style.use("seaborn-v0_8-whitegrid")
    HAS_SNS = False

mpl.rcParams.update({
    "figure.figsize":    (10, 6),
    "figure.dpi":         120,
    "font.size":           13,
    "axes.titlesize":      15,
    "axes.labelsize":      13,
    "xtick.labelsize":     11,
    "ytick.labelsize":     11,
    "legend.fontsize":     11,
    "legend.framealpha":   0.85,
    "lines.linewidth":      2.0,
    "axes.spines.top":     False,
    "axes.spines.right":   False,
    "savefig.bbox":       "tight",
    "savefig.dpi":         150,
})
np.random.seed(42)
print("Plot setup complete.")

Code cell 3

import numpy as np
import matplotlib
matplotlib.use("Agg")
import matplotlib.pyplot as plt
import matplotlib.patches as mpatches
import itertools, math, collections

HAS_NX = False
try:
    import networkx as nx
    HAS_NX = True
except ImportError:
    pass

# Wong colorblind-safe palette (notes VISUALIZATION_GUIDE)
WONG = ["#E69F00","#56B4E9","#009E73","#F0E442",
        "#0072B2","#D55E00","#CC79A7","#000000"]

plt.rcParams.update({
    "figure.dpi": 100,
    "axes.prop_cycle": plt.cycler(color=WONG),
})

print("Setup complete. NetworkX available:", HAS_NX)

1. Graph Objects and Adjacency Matrices

A graph $G = (V, E)$ is stored as an adjacency matrix $A$ where $A_{ij} = 1$ if $\{i,j\} \in E$ and 0 otherwise. For an undirected simple graph $A$ is symmetric with zero diagonal.

Code cell 5

# Build a small example graph: the "house" graph
# Vertices: 0,1,2,3,4  (base square + roof peak)
#   0 - 1
#   |   |
#   3 - 2
#    \ /
#     4  (roof peak)

edges_house = [(0,1),(1,2),(2,3),(3,0),(3,4),(2,4)]
n = 5
A_house = np.zeros((n, n), dtype=int)
for u, v in edges_house:
    A_house[u, v] = 1
    A_house[v, u] = 1

print("Adjacency matrix A:")
print(A_house)
print(f"\n|V| = {n},  |E| = {len(edges_house)}")

Code cell 6

# Visualise the house graph
if HAS_NX:
    G_house = nx.Graph()
    G_house.add_nodes_from(range(5))
    G_house.add_edges_from(edges_house)
    pos = {0:(0,1), 1:(1,1), 2:(1,0), 3:(0,0), 4:(0.5, 1.8)}

    fig, ax = plt.subplots(figsize=(4,4))
    nx.draw_networkx(G_house, pos=pos, ax=ax,
                     node_color=WONG[1], node_size=600,
                     edge_color=WONG[7], font_color="white", font_size=12)
    ax.set_title("House graph $G_{\\text{house}}$", fontsize=13)
    ax.axis("off")
    plt.tight_layout()
    plt.savefig("/tmp/house_graph.png")
    plt.show()
    print("House graph saved.")
else:
    print("NetworkX not available; skipping visualisation.")

2. Degree, Handshaking Lemma, and Degree Sequences

The degree of vertex $v_i$ is $\deg(v_i) = \sum_j A_{ij}$ (the row sum).

Handshaking Lemma: $\sum_v \deg(v) = 2|E|$ .

A degree sequence is the non-increasing list of vertex degrees.

Code cell 8

# Compute degrees from adjacency matrix
degrees = A_house.sum(axis=1)
print("Degrees:", degrees)
print("Degree sequence (sorted):", sorted(degrees, reverse=True))
print()
print(f"Sum of degrees = {degrees.sum()}")
print(f"2 * |E|        = {2 * len(edges_house)}")
print("Handshaking lemma holds:", degrees.sum() == 2 * len(edges_house))

Code cell 9

# Erdős-Gallai: is (3,3,2,2,2) a valid degree sequence?
def is_graphic(seq):
    """Erdős-Gallai theorem: check if a degree sequence is graphical."""
    s = sorted(seq, reverse=True)
    n = len(s)
    if sum(s) % 2 != 0:
        return False
    for k in range(1, n+1):
        lhs = sum(s[:k])
        rhs = k*(k-1) + sum(min(s[i], k) for i in range(k, n))
        if lhs > rhs:
            return False
    return True

test_seqs = [
    ([3,3,2,2,2], True),
    ([3,3,3,3],   True),   # K_4
    ([3,2,1,0],   False),  # odd sum
    ([2,2,2,1,1], False),  # fails Erdős-Gallai
]
for seq, expected in test_seqs:
    result = is_graphic(seq)
    status = "OK" if result == expected else "FAIL"
    print(f"  {seq}  →  graphical={result}  [{status}]")

Code cell 10

# Degree distribution bar chart
if HAS_NX:
    G_ba = nx.barabasi_albert_graph(200, 2, seed=42)
    deg_seq = sorted([d for _, d in G_ba.degree()], reverse=True)
    deg_counts = collections.Counter(deg_seq)
    ks = sorted(deg_counts)
    counts = [deg_counts[k] for k in ks]

    fig, axes = plt.subplots(1, 2, figsize=(9, 3.5))

    axes[0].bar(ks, counts, color=WONG[0], edgecolor=WONG[7], linewidth=0.5)
    axes[0].set_xlabel("Degree $k$"); axes[0].set_ylabel("Count")
    axes[0].set_title("Degree distribution — linear scale")

    axes[1].bar(ks, counts, color=WONG[1], edgecolor=WONG[7], linewidth=0.5)
    axes[1].set_xscale("log"); axes[1].set_yscale("log")
    axes[1].set_xlabel("Degree $k$"); axes[1].set_ylabel("Count")
    axes[1].set_title("Degree distribution — log-log (power law)")

    plt.suptitle("Barabási-Albert graph ($n=200$, $m=2$)", fontsize=12)
    plt.tight_layout()
    plt.savefig("/tmp/degree_dist.png")
    plt.show()
else:
    rng = np.random.default_rng(42)
    synthetic_degrees = np.maximum(2, rng.zipf(a=2.2, size=200))
    synthetic_degrees = np.minimum(synthetic_degrees, 40)
    deg_counts = collections.Counter(synthetic_degrees)
    ks = sorted(deg_counts)
    counts = [deg_counts[k] for k in ks]

    fig, axes = plt.subplots(1, 2, figsize=(9, 3.5))
    axes[0].bar(ks, counts, color=WONG[0], edgecolor=WONG[7], linewidth=0.5)
    axes[0].set_xlabel("Degree $k$"); axes[0].set_ylabel("Count")
    axes[0].set_title("Heavy-tail degree counts: linear scale")
    axes[1].bar(ks, counts, color=WONG[1], edgecolor=WONG[7], linewidth=0.5)
    axes[1].set_xscale("log"); axes[1].set_yscale("log")
    axes[1].set_xlabel("Degree $k$"); axes[1].set_ylabel("Count")
    axes[1].set_title("Heavy-tail degree counts: log-log scale")
    plt.suptitle("Synthetic heavy-tail degree sequence", fontsize=12)
    plt.tight_layout()
    plt.savefig("/tmp/degree_dist.png")
    plt.show()
    print("NetworkX not available; used a synthetic heavy-tail degree sequence.")

3. Walks, Trails, Paths, and Cycles

The number of walks of length $k$ from $i$ to $j$ equals $(A^k)_{ij}$ .

Term	Constraint
Walk	None
Trail	No repeated edges
Path	No repeated vertices
Cycle	Path with first = last

Code cell 12

# Count walks of length 1, 2, 3 using matrix powers
for k in [1, 2, 3]:
    Ak = np.linalg.matrix_power(A_house, k)
    print(f"A^{k}:")
    print(Ak)
    if k == 2:
        print(f"  (A^2)_{{00}} = {Ak[0,0]}  → walks of length 2 returning to vertex 0")
    print()

Code cell 13

# Number of triangles = tr(A^3) / 6
A3 = np.linalg.matrix_power(A_house, 3)
n_triangles = int(np.trace(A3)) // 6
print(f"tr(A^3) = {int(np.trace(A3))}")
print(f"Number of triangles in house graph = tr(A^3)/6 = {n_triangles}")
# Verify: triangles are {2,3,4} only → 1 triangle

4. Connectivity and Components

A graph is connected if every pair of vertices has a path between them.

BFS connectivity check: start from any vertex; if all $n$ vertices are reached, the graph is connected. The reachability matrix can be computed from the adjacency matrix: $G$ is connected iff $(I + A)^{n-1}$ has no zero entries (off-diagonal).

Code cell 15

def bfs_components(adj):
    """Return list of connected components via BFS."""
    n = len(adj)
    visited = [False] * n
    components = []
    for start in range(n):
        if not visited[start]:
            comp = []
            queue = collections.deque([start])
            visited[start] = True
            while queue:
                v = queue.popleft()
                comp.append(v)
                for u, connected in enumerate(adj[v]):
                    if connected and not visited[u]:
                        visited[u] = True
                        queue.append(u)
            components.append(comp)
    return components

comps = bfs_components(A_house)
print("Components of house graph:", comps)
print("Connected:", len(comps) == 1)

# Disconnected graph
A_disc = np.zeros((6,6), dtype=int)
for u, v in [(0,1),(1,2),(3,4)]:
    A_disc[u,v] = A_disc[v,u] = 1
comps2 = bfs_components(A_disc)
print("\nComponents of disconnected graph:", comps2)

Code cell 16

# Bridges: edges whose removal disconnects the graph
def find_bridges(adj):
    """Tarjan's bridge-finding algorithm O(V+E)."""
    n = len(adj)
    visited = [False]*n
    disc = [0]*n; low = [0]*n; timer = [0]
    bridges = []

    def dfs(u, parent):
        visited[u] = True
        disc[u] = low[u] = timer[0]; timer[0] += 1
        for v in range(n):
            if not adj[u][v]: continue
            if not visited[v]:
                dfs(v, u)
                low[u] = min(low[u], low[v])
                if low[v] > disc[u]:
                    bridges.append((u, v))
            elif v != parent:
                low[u] = min(low[u], disc[v])

    for i in range(n):
        if not visited[i]: dfs(i, -1)
    return bridges

bridges = find_bridges(A_house)
print("Bridges in house graph:", bridges)
# House graph: edge (3,4) and (2,4) are bridges (removing either splits the roof)

5. Special Graph Families

Key families: complete $K_n$ , cycle $C_n$ , path $P_n$ , complete bipartite $K_{m,n}$ , star $S_k$ , Petersen graph.

Code cell 18

def complete_graph(n):
    A = np.ones((n,n), dtype=int) - np.eye(n, dtype=int)
    return A

def cycle_graph(n):
    A = np.zeros((n,n), dtype=int)
    for i in range(n):
        A[i, (i+1)%n] = A[(i+1)%n, i] = 1
    return A

def path_graph(n):
    A = np.zeros((n,n), dtype=int)
    for i in range(n-1):
        A[i, i+1] = A[i+1, i] = 1
    return A

for name, G in [("K_4", complete_graph(4)),
                ("C_5", cycle_graph(5)),
                ("P_4", path_graph(4))]:
    degs = G.sum(axis=1)
    m = G.sum() // 2
    print(f"{name:4s}  n={len(G)}  m={m}  degrees={list(degs)}  regular={len(set(degs))==1}")

Code cell 19

if HAS_NX:
    families = {
        "$K_5$": nx.complete_graph(5),
        "$C_6$": nx.cycle_graph(6),
        "$K_{3,3}$": nx.complete_bipartite_graph(3,3),
        "Petersen": nx.petersen_graph(),
    }
    fig, axes = plt.subplots(1, 4, figsize=(14, 3.5))
    for ax, (name, G) in zip(axes, families.items()):
        layout = nx.shell_layout(G) if "K_5" in name or "C" in name else nx.spring_layout(G, seed=1)
        nx.draw_networkx(G, pos=layout, ax=ax,
                         node_color=WONG[2], node_size=300,
                         edge_color=WONG[7], with_labels=False)
        ax.set_title(name, fontsize=12); ax.axis("off")
    plt.suptitle("Special graph families", fontsize=13)
    plt.tight_layout()
    plt.savefig("/tmp/graph_families.png")
    plt.show()
else:
    def complete_bipartite_graph(m, n):
        A = np.zeros((m + n, m + n), dtype=int)
        A[:m, m:] = 1
        A[m:, :m] = 1
        return A

    def petersen_graph_adj():
        A = np.zeros((10, 10), dtype=int)
        for i in range(5):
            for u, v in [(i, (i + 1) % 5), (i, i + 5), (i + 5, ((i + 2) % 5) + 5)]:
                A[u, v] = A[v, u] = 1
        return A

    def circle_pos(n, radius=1.0, offset=np.pi / 2):
        return {i: (radius * np.cos(offset + 2 * np.pi * i / n),
                    radius * np.sin(offset + 2 * np.pi * i / n)) for i in range(n)}

    def draw_adj(A, pos, ax, node_size=220):
        for i in range(A.shape[0]):
            for j in range(i + 1, A.shape[1]):
                if A[i, j]:
                    ax.plot([pos[i][0], pos[j][0]], [pos[i][1], pos[j][1]], color=WONG[7], lw=1)
        xy = np.array([pos[i] for i in range(A.shape[0])])
        ax.scatter(xy[:, 0], xy[:, 1], s=node_size, color=WONG[2], edgecolor="white", zorder=3)
        ax.set_aspect("equal")
        ax.axis("off")

    families = {
        "$K_5$": (complete_graph(5), circle_pos(5)),
        "$C_6$": (cycle_graph(6), circle_pos(6)),
        "$K_{3,3}$": (complete_bipartite_graph(3, 3), {0: (-1, 1), 1: (-1, 0), 2: (-1, -1), 3: (1, 1), 4: (1, 0), 5: (1, -1)}),
        "Petersen": (petersen_graph_adj(), {**circle_pos(5, 1.35), **{i + 5: xy for i, xy in circle_pos(5, 0.62).items()}}),
    }
    fig, axes = plt.subplots(1, 4, figsize=(14, 3.5))
    for ax, (name, (A, pos)) in zip(axes, families.items()):
        draw_adj(A, pos, ax)
        ax.set_title(name, fontsize=12)
    plt.suptitle("Special graph families", fontsize=13)
    plt.tight_layout()
    plt.savefig("/tmp/graph_families.png")
    plt.show()
    print("NetworkX not available; drew graph families from adjacency matrices.")

6. Trees and Spanning Trees

A tree on $n$ vertices has exactly $n-1$ edges, is connected, and acyclic.

Cayley's formula: The number of labeled trees on $n$ vertices is $n^{n-2}$ .

Kirchhoff's Matrix Tree Theorem: The number of spanning trees equals any cofactor of the Laplacian $L = D - A$ .

Code cell 21

def laplacian(A):
    D = np.diag(A.sum(axis=1))
    return D - A

def count_spanning_trees(A):
    """Kirchhoff's theorem: delete row/col 0, take determinant of submatrix."""
    L = laplacian(A)
    L_sub = L[1:, 1:]
    return int(round(np.linalg.det(L_sub)))

# Verify Cayley's formula: K_n should have n^(n-2) spanning trees
for n in [2, 3, 4, 5]:
    A = complete_graph(n)
    kirchhoff = count_spanning_trees(A)
    cayley = n ** (n - 2)
    match = "OK" if kirchhoff == cayley else "FAIL"
    print(f"K_{n}: Kirchhoff={kirchhoff:4d}, Cayley n^(n-2)={cayley:4d}  [{match}]")

Code cell 22

# BFS spanning tree of house graph
def bfs_spanning_tree(adj, root=0):
    n = len(adj)
    visited = [False]*n
    tree_edges = []
    queue = collections.deque([root])
    visited[root] = True
    while queue:
        v = queue.popleft()
        for u in range(n):
            if adj[v][u] and not visited[u]:
                visited[u] = True
                tree_edges.append((v, u))
                queue.append(u)
    return tree_edges

tree = bfs_spanning_tree(A_house)
print("BFS spanning tree of house graph (root=0):", tree)
print(f"  |V|-1 = {n-1} edges, got {len(tree)} — correct:", len(tree) == n-1)

7. Bipartite Graphs

A graph is bipartite iff it contains no odd cycle, equivalently iff it is 2-colourable. BFS 2-colouring detects bipartiteness in $O(n+m)$ .

Code cell 24

def is_bipartite_bfs(adj):
    """BFS 2-colouring. Returns (True, colouring) or (False, None)."""
    n = len(adj)
    colour = [-1] * n
    for start in range(n):
        if colour[start] != -1: continue
        colour[start] = 0
        queue = collections.deque([start])
        while queue:
            v = queue.popleft()
            for u in range(n):
                if not adj[v][u]: continue
                if colour[u] == -1:
                    colour[u] = 1 - colour[v]
                    queue.append(u)
                elif colour[u] == colour[v]:
                    return False, None
    return True, colour

# C_4 is bipartite; K_3 is not; house graph has a triangle → not bipartite
tests = [
    ("C_4", cycle_graph(4)),
    ("C_5", cycle_graph(5)),
    ("K_{3,3}", np.block([[np.zeros((3,3),int), np.ones((3,3),int)],
                          [np.ones((3,3),int), np.zeros((3,3),int)]])),
    ("House", A_house),
]
for name, A in tests:
    bip, col = is_bipartite_bfs(A.tolist())
    print(f"  {name:8s}: bipartite={bip}", f"  colouring={col}" if bip else "")

8. Planar Graphs and Euler's Formula

Euler's formula for connected planar graphs: $n - m + f = 2$ .

For a simple connected planar graph with $n \geq 3$ : $m \leq 3n - 6$ . $K_5$ and $K_{3,3}$ violate these bounds, confirming non-planarity.

Code cell 26

def euler_planar_check(n, m):
    """Check Euler density bound m <= 3n-6 (necessary for planarity, n>=3)."""
    if n < 3:
        return True, "trivially planar"
    bound = 3*n - 6
    ok = m <= bound
    return ok, f"m={m} <= 3n-6={bound}: {'OK' if ok else 'VIOLATED (not planar)'}"

graphs = [
    ("K_4",    4,  6),
    ("K_5",    5, 10),
    ("C_6",    6,  6),
    ("K_{3,3}",6,  9),
    ("House",  5,  6),
    ("Petersen",10,15),
]
for name, n, m in graphs:
    ok, msg = euler_planar_check(n, m)
    print(f"  {name:10s}: {msg}")

Code cell 27

# Verify f = 2 - n + m for planar embeddings
# House graph: n=5, m=6 → f = 2 - 5 + 6 = 3 faces
# (outer face + two inner faces: bottom square split by diagonal? No — no diagonal.
#  Faces: bottom square interior, left triangle, right triangle, outer face = 3? Let's check)
# House: edges (0,1)(1,2)(2,3)(3,0)(3,4)(2,4)
# Faces: {0,1,2,3} square (1 face if planar), triangle {2,3,4}, outer face = 3 faces
n, m = 5, 6
f_expected = 2 - n + m
print(f"House graph: n={n}, m={m}")
print(f"Euler formula: f = 2 - n + m = 2 - {n} + {m} = {f_expected}")
print("Faces: outer face, inner square, triangle at roof → 3 ✓")

9. Graph Isomorphism and the Weisfeiler-Leman Test

Two graphs $G_1, G_2$ are isomorphic if there is a bijection $\phi: V_1 \to V_2$ preserving adjacency.

The 1-WL colour refinement algorithm iteratively refines vertex colours:

c^{(t+1)}(v) = \text{hash}\!\left(c^{(t)}(v),\ \{\!\{c^{(t)}(u) : u \in N(v)\}\!\}\right)

It can certify non-isomorphism but cannot certify isomorphism.

Code cell 29

def wl_1_refinement(adj, n_rounds=5):
    """1-WL colour refinement. Returns colour sequence per round."""
    n = len(adj)
    # Initial colouring: degree
    colours = [sum(adj[v]) for v in range(n)]
    history = [list(colours)]

    for _ in range(n_rounds):
        new_colours = []
        for v in range(n):
            nb_colours = tuple(sorted(colours[u] for u in range(n) if adj[v][u]))
            new_colours.append(hash((colours[v], nb_colours)) % (10**6))
        # Relabel to small integers for readability
        unique = sorted(set(new_colours))
        remap = {c: i for i, c in enumerate(unique)}
        colours = [remap[c] for c in new_colours]
        history.append(list(colours))
        if history[-1] == history[-2]:
            break
    return history

# Two non-isomorphic graphs with same degree sequence: C_6 vs two K_3
A_c6 = cycle_graph(6)

A_2k3 = np.zeros((6,6),int)
for u,v in [(0,1),(1,2),(2,0),(3,4),(4,5),(5,3)]:
    A_2k3[u,v] = A_2k3[v,u] = 1

h1 = wl_1_refinement(A_c6.tolist())
h2 = wl_1_refinement(A_2k3.tolist())

print("WL colouring of C_6:")
for i, c in enumerate(h1): print(f"  Round {i}: {c}")
print("\nWL colouring of 2xK_3:")
for i, c in enumerate(h2): print(f"  Round {i}: {c}")
print("\nFinal colours differ:", h1[-1] != h2[-1],
      "→ WL certifies non-isomorphism" if h1[-1] != h2[-1] else "→ WL cannot distinguish")

Code cell 30

# The WL failure case: two 3-regular non-isomorphic graphs (Shrikhande vs K_{4,4})
# We show two graphs WL cannot distinguish
# Simple example: two cospectral non-iso graphs (Saltire vs bowtie complement)
# Use: C_4 + K_1 vs K_{1,4} — same degree seq but different WL?

# Actually let's show the regular graph failure: two 2-regular graphs on same n
# C_6 is 2-regular; 2*K_3 is 2-regular. Already shown above.
# Let's also demonstrate graph-level WL (multiset of all colours)
def wl_graph_signature(adj, n_rounds=5):
    history = wl_1_refinement(adj, n_rounds)
    final = sorted(collections.Counter(history[-1]).items())
    return final

sig_c6   = wl_graph_signature(A_c6.tolist())
sig_2k3  = wl_graph_signature(A_2k3.tolist())
print("Graph signature C_6 :  ", sig_c6)
print("Graph signature 2xK_3:", sig_2k3)
print("Signatures differ:", sig_c6 != sig_2k3)

10. Graph Coloring and Chromatic Polynomial

The chromatic number $\chi(G)$ is the minimum number of colours needed for a proper vertex colouring.

The chromatic polynomial $P(G, k)$ counts proper $k$ -colourings. Deletion-contraction: $P(G, k) = P(G - e, k) - P(G/e, k)$ .

Code cell 32

def greedy_coloring(adj):
    """Greedy vertex coloring. Returns colour assignment."""
    n = len(adj)
    colour = [-1]*n
    for v in range(n):
        neighbour_colours = {colour[u] for u in range(n) if adj[v][u] and colour[u]>=0}
        c = 0
        while c in neighbour_colours: c += 1
        colour[v] = c
    return colour

for name, A in [("K_4", complete_graph(4)), ("C_5", cycle_graph(5)),
                ("House", A_house), ("C_6", cycle_graph(6))]:
    col = greedy_coloring(A.tolist())
    chi = max(col) + 1
    print(f"  {name:6s}: colours used = {chi}  colouring = {col}")

Code cell 33

# Chromatic polynomial via deletion-contraction (small graphs only)
# P(G, k) for paths and cycles — closed form verification
import sympy
k = sympy.Symbol("k")

def chrom_path(n):
    return k * (k - 1)**(n - 1)

def chrom_cycle(n):
    return (k - 1)**n + (-1)**n * (k - 1)

for n in [3, 4, 5, 6]:
    p_cycle = sympy.expand(chrom_cycle(n))
    # Verify chi: smallest positive integer root
    roots = [r for r in range(1, 5) if p_cycle.subs(k, r) > 0]
    chi = min(roots) if roots else "?"
    print(f"  P(C_{n}, k) = {p_cycle}   χ(C_{n}) = {chi}")

Code cell 34

if HAS_NX:
    # Visualise coloring of Petersen graph (χ=3)
    G_pet = nx.petersen_graph()
    col_pet = nx.coloring.greedy_color(G_pet, strategy="largest_first")
    n_col = max(col_pet.values()) + 1
    node_colours = [WONG[col_pet[v]] for v in G_pet.nodes()]

    fig, ax = plt.subplots(figsize=(5, 5))
    pos = nx.shell_layout(G_pet, nlist=[range(5,10), range(5)])
    nx.draw_networkx(G_pet, pos=pos, ax=ax,
                     node_color=node_colours, node_size=500,
                     edge_color=WONG[7], font_color="white", font_size=11)
    patches = [mpatches.Patch(color=WONG[i], label=f"Colour {i}") for i in range(n_col)]
    ax.legend(handles=patches, loc="lower right", fontsize=9)
    ax.set_title(f"Petersen graph — greedy colouring, $\\chi$ = {n_col}", fontsize=12)
    ax.axis("off")
    plt.tight_layout()
    plt.savefig("/tmp/petersen_coloring.png")
    plt.show()
else:
    def petersen_graph_adj():
        A = np.zeros((10, 10), dtype=int)
        for i in range(5):
            for u, v in [(i, (i + 1) % 5), (i, i + 5), (i + 5, ((i + 2) % 5) + 5)]:
                A[u, v] = A[v, u] = 1
        return A

    def greedy_color_adj(A):
        order = sorted(range(A.shape[0]), key=lambda v: -A[v].sum())
        color = {}
        for v in order:
            used = {color[u] for u in range(A.shape[0]) if A[v, u] and u in color}
            c = 0
            while c in used:
                c += 1
            color[v] = c
        return color

    A_pet = petersen_graph_adj()
    col_pet = greedy_color_adj(A_pet)
    n_col = max(col_pet.values()) + 1
    outer = {i: (1.4 * np.cos(np.pi / 2 + 2 * np.pi * i / 5), 1.4 * np.sin(np.pi / 2 + 2 * np.pi * i / 5)) for i in range(5)}
    inner = {i + 5: (0.62 * np.cos(np.pi / 2 + 2 * np.pi * i / 5), 0.62 * np.sin(np.pi / 2 + 2 * np.pi * i / 5)) for i in range(5)}
    pos = {**outer, **inner}
    fig, ax = plt.subplots(figsize=(5, 5))
    for i in range(10):
        for j in range(i + 1, 10):
            if A_pet[i, j]:
                ax.plot([pos[i][0], pos[j][0]], [pos[i][1], pos[j][1]], color=WONG[7], lw=1.3)
    xy = np.array([pos[i] for i in range(10)])
    ax.scatter(xy[:, 0], xy[:, 1], s=520, color=[WONG[col_pet[i]] for i in range(10)], edgecolor="white", zorder=3)
    for i, (x, y) in pos.items():
        ax.text(x, y, str(i), color="white", ha="center", va="center", fontsize=10, weight="bold")
    patches = [mpatches.Patch(color=WONG[i], label=f"Colour {i}") for i in range(n_col)]
    ax.legend(handles=patches, loc="lower right", fontsize=9)
    ax.set_title(f"Petersen graph greedy colouring, chi <= {n_col}", fontsize=12)
    ax.set_aspect("equal")
    ax.axis("off")
    plt.tight_layout()
    plt.savefig("/tmp/petersen_coloring.png")
    plt.show()
    print(f"NetworkX not available; fallback greedy coloring used {n_col} colours.")

11. Graph Motifs and Triangle Counting

Triangle count: $\Delta(G) = \frac{1}{6}\operatorname{tr}(A^3)$ .

Local clustering coefficient:

C(v) = \frac{|\{e_{uw}: u,w \in N(v), e_{uw}\in E\}|}{\binom{\deg(v)}{2}}

Clustering measures how "cliquish" a vertex's neighbourhood is.

Code cell 36

def count_triangles(A):
    A3 = np.linalg.matrix_power(A, 3)
    return int(np.trace(A3)) // 6

def local_clustering(A):
    n = len(A)
    C = []
    for v in range(n):
        neighbours = [u for u in range(n) if A[v][u]]
        d = len(neighbours)
        if d < 2:
            C.append(0.0)
            continue
        triangles_v = sum(A[u][w] for u in neighbours for w in neighbours if u < w)
        C.append(triangles_v / (d*(d-1)//2))
    return C

for name, A in [("K_4", complete_graph(4)), ("C_6", cycle_graph(6)),
                ("House", A_house)]:
    t = count_triangles(A)
    C = local_clustering(A.tolist())
    print(f"  {name:6s}: triangles={t}  clustering={[round(c,3) for c in C]}  "
          f"avg_C={round(sum(C)/len(C), 3)}")

Code cell 37

if HAS_NX:
    # Compare clustering in Erdős-Rényi vs Barabási-Albert
    G_er = nx.erdos_renyi_graph(100, 0.1, seed=0)
    G_ba = nx.barabasi_albert_graph(100, 3, seed=0)

    C_er = nx.average_clustering(G_er)
    C_ba = nx.average_clustering(G_ba)
    t_er = sum(nx.triangles(G_er).values()) // 3
    t_ba = sum(nx.triangles(G_ba).values()) // 3

    print(f"Erdős-Rényi G(100,0.1): avg_clustering={C_er:.3f}, triangles={t_er}")
    print(f"Barabási-Albert n=100,m=3: avg_clustering={C_ba:.3f}, triangles={t_ba}")
else:
    def er_graph_adj(n, p, rng):
        upper = rng.random((n, n)) < p
        A = np.triu(upper, 1).astype(int)
        return A + A.T

    def ba_graph_adj(n, m, rng):
        A = complete_graph(m + 1)
        for new in range(m + 1, n):
            deg = A.sum(axis=1).astype(float)
            probs = deg / deg.sum()
            targets = rng.choice(np.arange(new), size=m, replace=False, p=probs[:new] / probs[:new].sum())
            A = np.pad(A, ((0, 1), (0, 1)))
            for t in targets:
                A[new, t] = A[t, new] = 1
        return A

    def triangle_count(A):
        return int(np.trace(np.linalg.matrix_power(A, 3)) // 6)

    def average_clustering_adj(A):
        vals = []
        for v in range(A.shape[0]):
            nbrs = np.flatnonzero(A[v])
            k = len(nbrs)
            if k < 2:
                vals.append(0.0)
                continue
            sub = A[np.ix_(nbrs, nbrs)]
            vals.append(sub.sum() / (k * (k - 1)))
        return float(np.mean(vals))

    rng = np.random.default_rng(0)
    A_er = er_graph_adj(100, 0.1, rng)
    A_ba = ba_graph_adj(100, 3, rng)
    C_er = average_clustering_adj(A_er)
    C_ba = average_clustering_adj(A_ba)
    t_er = triangle_count(A_er)
    t_ba = triangle_count(A_ba)
    print(f"ER fallback G(100,0.1): avg_clustering={C_er:.3f}, triangles={t_er}")
    print(f"BA fallback n=100,m=3: avg_clustering={C_ba:.3f}, triangles={t_ba}")

12. Directed Graphs and DAGs

A DAG (directed acyclic graph) admits a topological ordering: a linear ordering of vertices such that all edges point forward.

Kahn's algorithm computes topological order in $O(n + m)$ via in-degree tracking.

Code cell 39

def kahn_topological_sort(adj_list, n):
    """Kahn's algorithm for topological sort of a DAG."""
    in_degree = [0]*n
    for u in range(n):
        for v in adj_list[u]:
            in_degree[v] += 1

    queue = collections.deque(v for v in range(n) if in_degree[v] == 0)
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in adj_list[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)

    if len(order) == n:
        return order          # valid DAG
    else:
        return None           # cycle detected

# Example: simple 5-node DAG
# 0→1, 0→2, 1→3, 2→3, 3→4
dag = {0:[1,2], 1:[3], 2:[3], 3:[4], 4:[]}
topo = kahn_topological_sort(dag, 5)
print("Topological order:", topo)

# With a cycle: 0→1→2→0
cyclic = {0:[1], 1:[2], 2:[0]}
topo_c = kahn_topological_sort(cyclic, 3)
print("Cyclic graph topological order:", topo_c, "(None = cycle detected)")

Code cell 40

if HAS_NX:
    # Visualise a small DAG (resembling a computation graph)
    G_dag = nx.DiGraph()
    G_dag.add_edges_from([(0,1),(0,2),(1,3),(2,3),(3,4),(2,4)])
    pos_dag = nx.nx_agraph.graphviz_layout(G_dag, prog="dot") if False else {
        0:(2,4), 1:(1,3), 2:(3,3), 3:(2,2), 4:(2,1)
    }
    fig, ax = plt.subplots(figsize=(4,5))
    nx.draw_networkx(G_dag, pos=pos_dag, ax=ax, with_labels=True,
                     node_color=WONG[0], node_size=600,
                     edge_color=WONG[7], arrows=True,
                     arrowstyle="-|>", arrowsize=20,
                     font_color="white", font_size=12)
    ax.set_title("Example DAG (computation graph)", fontsize=12)
    ax.axis("off")
    plt.tight_layout()
    plt.savefig("/tmp/dag_example.png")
    plt.show()
else:
    dag_edges = [(0,1),(0,2),(1,3),(2,3),(3,4),(2,4)]
    pos_dag = {0:(2,4), 1:(1,3), 2:(3,3), 3:(2,2), 4:(2,1)}
    fig, ax = plt.subplots(figsize=(4,5))
    for u, v in dag_edges:
        ax.annotate("", xy=pos_dag[v], xytext=pos_dag[u], arrowprops={"arrowstyle": "-|>", "color": WONG[7], "lw": 1.5})
    xy = np.array([pos_dag[i] for i in range(5)])
    ax.scatter(xy[:, 0], xy[:, 1], s=650, color=WONG[0], edgecolor="white", zorder=3)
    for i, (x, y) in pos_dag.items():
        ax.text(x, y, str(i), color="white", ha="center", va="center", fontsize=12, weight="bold")
    ax.set_title("Example DAG (computation graph)", fontsize=12)
    ax.set_aspect("equal")
    ax.axis("off")
    plt.tight_layout()
    plt.savefig("/tmp/dag_example.png")
    plt.show()
    print("NetworkX not available; drew DAG manually with Matplotlib arrows.")

Summary

Concept	Key formula / algorithm	Complexity
Degree	$\deg(v) = \sum_j A_{ij}$	$O(n)$ per vertex
Handshaking	$\sum \deg = 2m$	$O(n)$
Walk count	$(A^k)_{ij}$	$O(n^3)$ per power
Triangle count	$\operatorname{tr}(A^3)/6$	$O(n^3)$
Spanning trees	$\det(L_{00})$	$O(n^3)$
Connectivity	BFS/DFS	$O(n+m)$
Bipartiteness	BFS 2-colouring	$O(n+m)$
Topological sort	Kahn's algorithm	$O(n+m)$
Greedy colouring	Largest-first	$O(n+m)$
1-WL refinement	Multiset hashing	$O(n^2)$ per round

Next: 02-Graph-Representations/ covers adjacency lists, edge lists, and sparse matrix formats — the practical storage counterpart to this theoretical foundation.