Graph Theory

Formal definition. An undirected graph G = (V, E) consists of a finite set V of vertices (also called nodes) and a set E of edges, where each edge is a 2-element subset {u, v} of V. A directed graph (digraph) G = (V, E) has edges that are ordered pairs (u, v), meaning there is an arrow from u to v but not necessarily the reverse.

The degree deg(v) of a vertex v in an undirected graph is the number of edges incident to it. In a digraph, we distinguish in-degree (arrows pointing in) from out-degree (arrows pointing out).

Handshaking Lemma. For any undirected graph G, the sum of all vertex degrees equals twice the number of edges: $$\sum_{v \in V} \deg(v) = 2|E|$$ Proof: every edge {u, v} contributes exactly 1 to deg(u) and exactly 1 to deg(v), so it contributes exactly 2 to the total sum. An immediate corollary: the number of odd-degree vertices is always even.

Representation. Two canonical ways to represent a graph in memory:

1. Adjacency matrix: an |V|×|V| boolean matrix A where A[i][j] = 1 iff {i,j} is an edge. O(|V|²) space; O(1) edge lookup; O(|V|) to iterate neighbors.
2. Adjacency list: an array of |V| lists, where list i contains all neighbors of vertex i. O(|V|+|E|) space; O(deg(v)) to iterate neighbors; preferred for sparse graphs.

Special graphs. A complete graph Kₙ has every pair of distinct vertices connected by an edge; |E| = n(n−1)/2. A path graph Pₙ is a sequence of n vertices connected in a line. A cycle graph Cₙ is a closed loop of n vertices. A bipartite graph has its vertices split into two groups with edges only between groups (formalized later).

# Adjacency list representation in Python
from collections import defaultdict

class Graph:
    def __init__(self, directed=False):
        self.adj = defaultdict(set)
        self.directed = directed

    def add_edge(self, u, v):
        self.adj[u].add(v)
        if not self.directed:
            self.adj[v].add(u)

    def degree(self, v):
        return len(self.adj[v])

    def handshaking_check(self):
        total = sum(self.degree(v) for v in self.adj)
        edges = sum(len(nbrs) for nbrs in self.adj.values())
        if not self.directed:
            edges //= 2
        return total == 2 * edges  # always True

# Example: K4 (complete graph on 4 vertices)
g = Graph()
for u in range(4):
    for v in range(u+1, 4):
        g.add_edge(u, v)
print([g.degree(v) for v in range(4)])  # [3, 3, 3, 3]

Walks and paths. A walk in a graph is a sequence of vertices v₀, v₁, …, vₖ where each consecutive pair {vᵢ, vᵢ₊₁} is an edge. The length of the walk is k (the number of edges traversed). A trail is a walk in which all edges are distinct. A path is a walk in which all vertices (and therefore all edges) are distinct. The distance d(u, v) between two vertices is the length of a shortest path between them; if no path exists the distance is ∞.

Cycles. A cycle (or circuit) is a closed walk v₀, v₁, …, vₖ = v₀ where v₀, v₁, …, vₖ₋₁ are all distinct and k ≥ 3. A graph with no cycles is acyclic. An undirected acyclic connected graph is a tree (formalized later).

Girth. The girth of a graph is the length of its shortest cycle. Graphs with high girth have a tree-like local structure and arise naturally in coding theory and extremal graph theory.

Shortest paths. Breadth-first search (BFS) computes shortest paths in an unweighted graph in O(|V|+|E|) time. The key invariant: when BFS first visits a vertex v at distance d, it has found a shortest path. Dijkstra's algorithm extends this to non-negative weighted graphs in O((|V|+|E|) log |V|) with a priority queue.

Detecting cycles. In an undirected graph, a DFS detects a cycle iff it encounters a back edge (an edge to an already-visited ancestor). In a directed graph, a DFS detects a cycle iff it finds a back edge in the DFS forest.

from collections import deque

def bfs_shortest_path(adj, source, target):
    """Returns shortest-path distance and the path itself."""
    dist = {source: 0}
    parent = {source: None}
    queue = deque([source])
    while queue:
        u = queue.popleft()
        if u == target:
            # Reconstruct path
            path = []
            while u is not None:
                path.append(u)
                u = parent[u]
            return dist[target], list(reversed(path))
        for v in adj[u]:
            if v not in dist:
                dist[v] = dist[u] + 1
                parent[v] = u
                queue.append(v)
    return float('inf'), []   # no path

def has_cycle_undirected(adj, vertices):
    visited = set()
    def dfs(v, parent):
        visited.add(v)
        for w in adj[v]:
            if w not in visited:
                if dfs(w, v): return True
            elif w != parent:   # back edge found
                return True
        return False
    return any(dfs(v, -1) for v in vertices if v not in visited)

Connected graphs. An undirected graph is connected if there exists a path between every pair of vertices. A connected component is a maximal connected subgraph — it is as large as possible while remaining connected. Every graph decomposes uniquely into its connected components.

Strong connectivity in digraphs. In a directed graph, vertex u can reach v if there is a directed path from u to v. A digraph is strongly connected if every vertex can reach every other vertex. A strongly connected component (SCC) is a maximal strongly connected subgraph. Tarjan's algorithm and Kosaraju's algorithm both find all SCCs in O(|V|+|E|) time.

Cut vertices and bridges. A cut vertex (or articulation point) is a vertex whose removal disconnects the graph. A bridge is an edge whose removal disconnects the graph. These are exactly the structural bottlenecks of a network — the single points of failure. Both can be found in O(|V|+|E|) using DFS and tracking 'discovery time' vs 'low value' (the lowest discovery time reachable from a subtree).

k-Connectivity. A graph is k-vertex-connected if it has more than k vertices and remains connected after removing any k−1 vertices. Menger's theorem provides a deep characterization: the maximum number of vertex-disjoint paths between any pair s, t equals the minimum vertex cut separating them — a minimax theorem relating paths to cuts.

Union-Find. For static connectivity queries, Union-Find (Disjoint Set Union) supports 'are u and v in the same component?' in nearly O(1) amortized time after O(|E| α(|V|)) preprocessing, where α is the inverse Ackermann function (effectively constant).

# Kosaraju's algorithm for strongly connected components
def kosaraju_scc(n, adj):
    """adj: adjacency list for directed graph on vertices 0..n-1"""
    radj = [[] for _ in range(n)]  # reversed graph
    for u in range(n):
        for v in adj[u]:
            radj[v].append(u)

    visited = [False] * n
    finish_order = []

    def dfs1(u):            # fill finish order
        stack = [(u, iter(adj[u]))]
        visited[u] = True
        while stack:
            v, it = stack[-1]
            try:
                w = next(it)
                if not visited[w]:
                    visited[w] = True
                    stack.append((w, iter(adj[w])))
            except StopIteration:
                finish_order.append(v)
                stack.pop()

    for u in range(n):
        if not visited[u]:
            dfs1(u)

    comp = [-1] * n
    c = 0
    def dfs2(u, label):     # assign components on reversed graph
        comp[u] = label
        for v in radj[u]:
            if comp[v] == -1:
                dfs2(v, label)

    for u in reversed(finish_order):
        if comp[u] == -1:
            dfs2(u, c)
            c += 1
    return comp, c          # component label for each vertex

Trees. A tree is a connected acyclic undirected graph. Trees are the simplest connected graphs and the backbone of countless data structures (binary search trees, heaps, tries, syntax trees). The following statements about a graph T on n vertices are all equivalent — any one implies all others:

1. T is connected and acyclic.
2. T is connected and has exactly n−1 edges.
3. T is acyclic and has exactly n−1 edges.
4. Any two vertices are connected by exactly one path.
5. T is connected, but removing any edge disconnects it.
6. T is acyclic, but adding any edge creates exactly one cycle.

Proof sketch of (1)⟺(2): Induction on n. For n=1 trivially true. For n>1, any tree has a leaf (a vertex of degree 1); remove it and the result is a tree on n−1 vertices with n−2 edges.

Rooted trees and forests. A rooted tree designates one vertex as the root; this gives every edge a natural parent-child direction. A forest is a disjoint union of trees (an acyclic graph, possibly disconnected); a forest on n vertices and k components has n−k edges.

Spanning trees. A spanning tree of a connected graph G is a subgraph that is a tree and includes all vertices of G. Every connected graph has at least one spanning tree. The number of labeled spanning trees of Kₙ is nⁿ⁻² (Cayley's formula).

Minimum spanning trees (MST). Given a weighted graph, the MST is the spanning tree with minimum total edge weight. Kruskal's algorithm sorts edges by weight and greedily adds each edge that does not form a cycle (using Union-Find), in O(|E| log |E|). Prim's algorithm grows a tree from a seed vertex, always adding the cheapest edge crossing the cut, in O(|E| log |V|) with a heap. Both are correct by the cut property: for any cut (S, V−S) of the graph, the minimum-weight crossing edge is in some MST.

# Kruskal's MST algorithm
def kruskal_mst(n, edges):
    """edges: list of (weight, u, v). Returns MST edge list."""
    parent = list(range(n))
    rank   = [0] * n

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]  # path compression
            x = parent[x]
        return x

    def union(a, b):
        ra, rb = find(a), find(b)
        if ra == rb: return False          # same component = cycle
        if rank[ra] < rank[rb]: ra, rb = rb, ra
        parent[rb] = ra
        if rank[ra] == rank[rb]: rank[ra] += 1
        return True

    mst = []
    for w, u, v in sorted(edges):
        if union(u, v):
            mst.append((w, u, v))
        if len(mst) == n - 1:
            break
    return mst

Definition. A graph G = (V, E) is bipartite if its vertex set V can be partitioned into two disjoint sets L and R (called the two sides or parts) such that every edge connects a vertex in L to a vertex in R. No edges exist within L or within R.

Examples everywhere. The graph of students on one side and courses on the other, with edges meaning 'enrolled', is bipartite. The graph of jobs and workers matched to jobs is bipartite. DNA matching (gene ↔ phenotype), recommendation systems (user ↔ item), and scheduling (task ↔ time-slot) are all naturally bipartite.

Characterization theorem. A graph is bipartite if and only if it contains no odd-length cycle. The 'only if' direction is easy: any cycle in a bipartite graph must alternate between L and R, so it must have even length. The 'if' direction: try to 2-color the graph by BFS — assign each vertex the opposite color of its parent. If this succeeds without conflict, we have a valid bipartition. If it fails, we have found an odd cycle.

2-coloring and BFS. BFS-based 2-coloring runs in O(|V|+|E|) and simultaneously verifies bipartiteness and produces the partition.

Matching. A matching in a bipartite graph is a set of pairwise non-adjacent edges — each vertex is matched to at most one partner. A maximum matching is a matching of maximum cardinality. Hall's theorem characterizes when a perfect matching (one that saturates all of L) exists: for every subset S ⊆ L, the neighborhood N(S) satisfies |N(S)| ≥ |S|. The augmenting path algorithm (Hopcroft-Karp) finds a maximum bipartite matching in O(√|V| · |E|).

König's theorem. In a bipartite graph, the size of the maximum matching equals the size of the minimum vertex cover (a set of vertices that touches every edge). This is a beautiful LP duality result.

from collections import deque

def is_bipartite(adj, vertices):
    """BFS 2-coloring. Returns (True, color_dict) or (False, {})."""
    color = {}
    for start in vertices:
        if start in color:
            continue
        color[start] = 0
        queue = deque([start])
        while queue:
            u = queue.popleft()
            for v in adj[u]:
                if v not in color:
                    color[v] = 1 - color[u]
                    queue.append(v)
                elif color[v] == color[u]:  # odd cycle!
                    return False, {}
    return True, color

# Example: C6 is bipartite (even cycle)
adj6 = {0:[1,5], 1:[0,2], 2:[1,3], 3:[2,4], 4:[3,5], 5:[4,0]}
print(is_bipartite(adj6, range(6)))   # (True, ...)

# C5 is not bipartite (odd cycle)
adj5 = {0:[1,4], 1:[0,2], 2:[1,3], 3:[2,4], 4:[3,0]}
print(is_bipartite(adj5, range(5)))   # (False, {})

The Königsberg problem. In 1736, the city of Königsberg (now Kaliningrad) had seven bridges connecting two islands and two riverbanks. Citizens wondered: can you take a walk that crosses each bridge exactly once? Euler modeled each landmass as a vertex and each bridge as an edge, and proved it is impossible — inventing graph theory in the process.

Definitions. An Eulerian trail (or Euler path) is a walk that traverses every edge exactly once. An Eulerian circuit is a closed Eulerian trail (starts and ends at the same vertex).

Euler's theorem. For a connected undirected graph:

• An Eulerian circuit exists if and only if every vertex has even degree.
• An Eulerian trail (not necessarily closed) exists if and only if there are exactly 0 or 2 vertices of odd degree. If 2 odd-degree vertices exist, the trail starts at one and ends at the other.

Proof sketch (necessity for circuit): in any Eulerian circuit, every time the circuit enters a vertex it must leave it, contributing 2 to the degree. Necessity is clear. Sufficiency is proved constructively by Hierholzer's algorithm.

Why Königsberg fails. All four landmasses have odd degree (3, 3, 3, 5), so not even an Eulerian trail exists.

Hierholzer's algorithm. Start at any vertex, follow edges (removing them) until you return to the start — this gives a closed walk but may not cover all edges. If any vertex on this walk has unused edges, start a new sub-circuit from there, and splice it in. Repeat until all edges are used. Time complexity: O(|E|).

Directed analogue. A directed graph has an Eulerian circuit iff it is strongly connected and every vertex has in-degree equal to out-degree. It has an Eulerian trail iff exactly one vertex has out-degree − in-degree = 1 (start), exactly one has in-degree − out-degree = 1 (end), and all others are balanced.

def hierholzer_euler_circuit(adj_input, start):
    """
    Hierholzer's algorithm for Eulerian circuit.
    adj_input: dict mapping vertex -> list of neighbors (multigraph ok).
    Modifies a copy; returns circuit as list of vertices.
    Precondition: graph is connected and every vertex has even degree.
    """
    from collections import defaultdict
    adj = defaultdict(list)
    for u, nbrs in adj_input.items():
        adj[u] = list(nbrs)   # copy

    circuit = []
    stack = [start]
    while stack:
        v = stack[-1]
        if adj[v]:            # still has unused edges
            u = adj[v].pop()
            # remove reverse edge for undirected graph
            adj[u].remove(v)
            stack.append(u)
        else:
            circuit.append(stack.pop())
    return circuit

# K4 has all degrees = 3 (odd) — no Euler circuit
# Try a graph where all degrees are even: two triangles sharing an edge
# 0-1-2-0-3-4-0 style
adj = {0:[1,2,3,4], 1:[0,2], 2:[1,0], 3:[0,4], 4:[3,0]}
print(hierholzer_euler_circuit(adj, 0))

Definition. A Hamiltonian path is a path that visits every vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits every vertex exactly once. A graph that contains a Hamiltonian cycle is called Hamiltonian.

Contrast with Euler. Euler paths care about edges (traverse each once); Hamilton paths care about vertices (visit each once). This difference is profound: Euler paths have an elegant polynomial-time characterization and algorithm, while Hamiltonian paths are NP-complete — no efficient algorithm is known, and most researchers believe none exists. This asymmetry is one of the great mysteries of computer science.

Sufficient conditions (not necessary). Several theorems guarantee Hamiltonicity:

• Dirac's theorem (1952): If every vertex of a simple graph on n ≥ 3 vertices has degree ≥ n/2, then the graph has a Hamiltonian cycle.
• Ore's theorem (1960): If for every pair of non-adjacent vertices u, v we have deg(u) + deg(v) ≥ n, then the graph has a Hamiltonian cycle. Both are sufficient but not necessary; no clean necessary-and-sufficient condition is known.

Connection to TSP. The Travelling Salesman Problem (TSP) asks for the minimum-weight Hamiltonian cycle in a complete weighted graph. It is NP-hard to solve exactly and NP-hard even to approximate better than a constant factor (for the general case). For metric TSP, Christofides' algorithm achieves a 3/2-approximation.

Backtracking algorithm. In practice, Hamiltonian cycle is solved with backtracking + pruning. The Warnsdorff heuristic for the knight's tour (Hamiltonian path on the chess knight graph) is a greedy approach: always move to the square with fewest onward moves.

def hamiltonian_cycle(adj, n):
    """
    Backtracking search for Hamiltonian cycle.
    adj: adjacency matrix (list of lists). Returns path or None.
    """
    path = [0]          # start at vertex 0
    visited = [False] * n
    visited[0] = True

    def backtrack():
        if len(path) == n:
            # Check if last vertex connects back to start
            return adj[path[-1]][path[0]] == 1
        last = path[-1]
        for v in range(n):
            if not visited[v] and adj[last][v] == 1:
                visited[v] = True
                path.append(v)
                if backtrack():
                    return True
                path.pop()
                visited[v] = False
        return False

    if backtrack():
        return path + [path[0]]
    return None

# K4 adjacency matrix — Hamiltonian cycle exists
K4 = [[0,1,1,1],[1,0,1,1],[1,1,0,1],[1,1,1,0]]
print(hamiltonian_cycle(K4, 4))   # e.g. [0, 1, 2, 3, 0]

Definition. A graph is planar if it can be drawn in the plane (or equivalently, on a sphere) such that no two edges cross. Such a drawing is called a planar embedding or plane graph. Planarity is a topological property: it depends only on the graph's combinatorial structure, not on any particular drawing.

Euler's formula. For any connected plane graph with V vertices, E edges, and F faces (including the unbounded outer face): V − E + F = 2. This is one of the most elegant results in all of mathematics, and it extends to any simply connected surface. For a disconnected plane graph with C components: V − E + F = C + 1.

Consequences. From Euler's formula, any planar graph with V ≥ 3 vertices satisfies E ≤ 3V − 6. For triangle-free planar graphs: E ≤ 2V − 4. These bounds give us immediate non-planarity certificates.

K5 and K3,3 are not planar. K5 has 5 vertices and 10 edges; 3V−6 = 9 < 10, violating the bound. K3,3 is triangle-free with 6 vertices and 9 edges; 2V−4 = 8 < 9.

Kuratowski's theorem (1930). A graph is planar if and only if it contains no subgraph that is a subdivision of K5 or K3,3 (a subdivision replaces edges with paths). This is both a beautiful structure theorem and a certificate of non-planarity.

Wagner's theorem. Equivalently, a graph is planar iff it has no minor isomorphic to K5 or K3,3. (A minor is obtained by contracting, deleting, and isolating vertices.)

Testing planarity. The Hopcroft-Tarjan algorithm tests planarity in O(V+E) using DFS and the left-right planarity condition.

# Euler's formula verification for a known planar graph
# Consider a cube graph: V=8, E=12, F=6 (including outer face)
# V - E + F = 8 - 12 + 6 = 2  ✓

# Check necessary condition E <= 3V - 6 for planarity
def planar_necessary(V, E):
    """Returns False if the edge bound rules out planarity."""
    if V < 3:
        return True   # trivially planar
    return E <= 3 * V - 6

# K5: 5 vertices, 10 edges
print(planar_necessary(5, 10))   # False -> cannot be planar

# Petersen graph: 10 vertices, 15 edges
print(planar_necessary(10, 15))  # True -> not ruled out by this bound
# (Petersen graph is actually non-planar, but needs Kuratowski proof)

# K4: 4 vertices, 6 edges -> 3*4-6 = 6 >= 6: passes necessary check
print(planar_necessary(4, 6))    # True (K4 is indeed planar)

Definition. A proper k-coloring of a graph G assigns one of k colors to each vertex such that no two adjacent vertices share a color. The chromatic number χ(G) is the minimum k for which G is k-colorable.

Basic bounds. χ(G) ≥ ω(G) (clique number: the largest complete subgraph) since a complete subgraph requires as many colors as it has vertices. χ(G) ≤ Δ(G)+1 (Brooks' theorem refines this: χ(G) ≤ Δ(G) unless G is a complete graph or an odd cycle, in which case χ(G) = Δ(G)+1).

Two-coloring = bipartite. χ(G) = 1 iff G has no edges. χ(G) ≤ 2 iff G is bipartite (no odd cycles). χ(G) = 3 iff G contains an odd cycle but no triangle (this alone is a hard problem — triangle detection is O(n^ω) where ω < 2.37).

The four-color theorem. Every planar graph is 4-colorable (χ ≤ 4). Proved by Appel and Haken in 1976 using an exhaustive computer-assisted case analysis of 1936 'unavoidable' configurations — the first major theorem proved with substantial computer assistance. A simpler proof by Robertson, Sanders, Seymour, and Thomas appeared in 1997. The five-color theorem (χ ≤ 5 for planar graphs) has an elegant manual proof.

Greedy coloring. Process vertices in some order; assign the smallest color not used by already-colored neighbors. Uses at most Δ+1 colors. The result depends heavily on the ordering; the optimal ordering is NP-hard to find in general.

Applications. Register allocation in compilers is graph coloring: vertices are live ranges, edges mean 'live at the same time', colors are registers. Map coloring, scheduling, and frequency assignment in wireless networks are all coloring problems.

Edge coloring. A proper edge coloring assigns colors to edges such that no two edges sharing a vertex have the same color. The minimum number of colors needed is the chromatic index χ'(G). Vizing's theorem: χ'(G) is either Δ(G) or Δ(G)+1.

def greedy_coloring(adj, vertices):
    """
    Greedy vertex coloring. Returns dict: vertex -> color (0-indexed).
    Uses at most Delta+1 colors.
    """
    color = {}
    for v in vertices:
        neighbor_colors = {color[u] for u in adj[v] if u in color}
        c = 0
        while c in neighbor_colors:
            c += 1
        color[v] = c
    return color

def chromatic_bound(adj, vertices):
    """Upper bound: Delta + 1."""
    delta = max((len(adj[v]) for v in vertices), default=0)
    return delta + 1

# Petersen graph: Delta=3, chi=3
petersen_adj = {
    0:[1,4,5], 1:[0,2,6], 2:[1,3,7], 3:[2,4,8], 4:[3,0,9],
    5:[0,7,8], 6:[1,8,9], 7:[2,9,5], 8:[3,5,6], 9:[4,6,7]
}
coloring = greedy_coloring(petersen_adj, range(10))
num_colors = len(set(coloring.values()))
print(f"Colors used: {num_colors}")   # 3
print(f"Bound Delta+1: {chromatic_bound(petersen_adj, range(10))}")  # 4

Isomorphism. Two graphs G = (V, E) and H = (V', E') are isomorphic (G ≅ H) if there exists a bijection φ: V → V' that preserves adjacency: {u,v} ∈ E iff {φ(u), φ(v)} ∈ E'. Isomorphic graphs are 'the same graph up to relabeling of vertices.'

Graph isomorphism (GI) problem. Given two graphs, are they isomorphic? Determining the complexity of GI is a famous open problem. It is not known to be in P or NP-complete. It lies in NP (a bijection is a polynomial-time checkable certificate). Babai's breakthrough in 2015 showed GI can be solved in quasipolynomial time (exp(polylog n)).

Invariants. To show two graphs are not isomorphic, it suffices to find an invariant that differs. Useful invariants: number of vertices, number of edges, degree sequence, chromatic number, number of triangles, girth, diameter. Two graphs with identical degree sequences may still be non-isomorphic (e.g., two non-isomorphic graphs on 6 vertices both with degree sequence [3,3,2,2,2,2] exist).

Automorphisms. An isomorphism from a graph to itself is an automorphism. The set of all automorphisms of G forms a group Aut(G) under composition. Highly symmetric graphs (like Kₙ, Petersen graph, hypercubes) have large automorphism groups, which often makes them good error-correcting codes and network topologies.

# Check graph isomorphism by comparing degree sequences (necessary, not sufficient)
def degree_sequence(adj, vertices):
    return sorted(len(adj[v]) for v in vertices)

# Two non-isomorphic trees on 6 vertices — same vertex count, same edge count
# Path P6 vs "caterpillar" (star K1,4 with one extra leaf)
adj_P6 = {0:[1],1:[0,2],2:[1,3],3:[2,4],4:[3,5],5:[4]}
adj_cat = {0:[1,2,3,4],1:[0],2:[0,5],3:[0],4:[0],5:[2]}

ds_P6 = degree_sequence(adj_P6, range(6))
ds_cat = degree_sequence(adj_cat, range(6))

print(ds_P6)   # [1, 1, 2, 2, 2, 2]
print(ds_cat)  # [1, 1, 1, 1, 2, 4] — different! not isomorphic

# When degree sequences match, you need deeper invariants
# (spectrum, subgraph counts, Weisfeiler-Leman refinement, ...)

Directed acyclic graphs (DAGs). A DAG is a directed graph with no directed cycles. DAGs are the natural model for dependency relationships: course prerequisites, build systems (Makefiles), spreadsheet cell dependencies, Git commit histories, and event causality. Every DAG has at least one source (vertex with in-degree 0) and at least one sink (vertex with out-degree 0).

Topological ordering. A topological sort of a DAG is a linear ordering of all vertices such that for every directed edge (u, v), vertex u appears before v. If the graph has a directed cycle, no topological sort exists. Kahn's algorithm: repeatedly remove a source vertex and its outgoing edges; if the graph empties completely, the removal order is a topological sort; if vertices remain, a cycle exists. DFS-based topological sort: finish vertices in DFS in reverse finish order.

Longest path in a DAG. Unlike general graphs (where longest path is NP-hard), the longest path in a DAG can be found in O(V+E) using dynamic programming in topological order. This is the basis of the critical path method in project scheduling.

Condensation. The condensation of a directed graph G is the DAG obtained by collapsing each SCC to a single vertex. This DAG summarizes the high-level structure of the graph and is foundational to algorithms on digraphs.

from collections import deque

def topological_sort_kahn(n, edges):
    """
    Kahn's algorithm. Returns topological order or detects cycle.
    edges: list of (u, v) directed edges on vertices 0..n-1.
    """
    in_deg = [0] * n
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        in_deg[v] += 1

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

    if len(order) == n:
        return order         # valid topological sort
    return None              # cycle detected

# Course prereqs: 0->2, 1->2, 2->3
print(topological_sort_kahn(4, [(0,2),(1,2),(2,3)]))
# e.g. [0, 1, 2, 3]

Flow networks. A flow network is a directed graph G = (V, E) with a source s, a sink t, and a non-negative capacity c(u,v) for each edge. A flow assigns a value f(u,v) to each edge satisfying: (1) capacity: 0 ≤ f(u,v) ≤ c(u,v); (2) conservation: for every non-source, non-sink vertex, flow in = flow out. The value of a flow is the net flow out of s.

Max-flow min-cut theorem. The maximum flow from s to t equals the minimum capacity of any s-t cut (a partition of V into S∋s and T∋t; cut capacity = sum of capacities of edges from S to T). This is one of the deepest and most useful theorems in combinatorics.

Ford-Fulkerson / Edmonds-Karp. Ford-Fulkerson repeatedly finds augmenting paths in the residual graph (which includes reverse edges) and pushes flow along them. Edmonds-Karp specializes to BFS for augmenting paths, giving O(VE²) runtime.

Applications. Maximum bipartite matching reduces to max flow: add a super-source connected to all L-vertices and a super-sink connected from all R-vertices, set all capacities to 1, and find max flow. The flow value equals the matching size. This also proves König's theorem. Other applications: circulation with demands, project selection, image segmentation (min-cut), and multi-commodity flow.

Menger's theorem (revisited). The maximum number of edge-disjoint paths from s to t equals the minimum number of edges in an s-t cut — a direct consequence of max-flow min-cut with unit capacities.

from collections import deque

def edmonds_karp(n, cap, s, t):
    """
    Max flow via BFS augmenting paths (Edmonds-Karp).
    cap: n×n capacity matrix. Returns max flow value.
    """
    flow = [[0]*n for _ in range(n)]
    total = 0

    def bfs_path():
        parent = [-1] * n
        parent[s] = s
        queue = deque([s])
        while queue and parent[t] == -1:
            u = queue.popleft()
            for v in range(n):
                if parent[v] == -1 and cap[u][v] - flow[u][v] > 0:
                    parent[v] = u
                    queue.append(v)
        return parent if parent[t] != -1 else None

    while True:
        parent = bfs_path()
        if parent is None: break
        # Find bottleneck
        path_flow, v = float('inf'), t
        while v != s:
            u = parent[v]
            path_flow = min(path_flow, cap[u][v] - flow[u][v])
            v = u
        # Augment
        v = t
        while v != s:
            u = parent[v]
            flow[u][v] += path_flow
            flow[v][u] -= path_flow
            v = u
        total += path_flow
    return total