Graph Theory, Spectral Laplacians & Edmonds-Karp Network Flow

Graphs are the universal discrete structure modeling relationships, dependencies, and communication topologies across computer systems. From compiler Control Flow Graphs (CFGs) and dependency resolution trees in build systems, to distributed consensus quorums and internet autonomous system (BGP) routing, graph algorithms are foundational to computer science. Advanced graph theory unites combinatorial graph traversal with linear algebra, spectral matrix analysis, and network flow optimization.

1. Graph Foundations & Topological Invariants#

A Graph G = (V, E) consists of a finite set of Vertices (or nodes) V and a set of Edges E ⊆ V × V. If edges have directional orientation (u, v) ≠ (v, u), the graph is Directed (a digraph); otherwise, it is Undirected.

> Mathematical Notation Primer:
> - '|V|' or 'n' denotes the number of vertices in graph G.
> - '|E|' or 'm' denotes the number of edges in graph G.
> - 'deg(v)' denotes the Degree of vertex v (the number of edges incident to v).
> - 'deg^+(v)' and 'deg^-(v)' denote Out-Degree and In-Degree in directed graphs.
> - 'λ_0, λ_1, ..., λ_{n-1}' denote the Eigenvalues of the Graph Laplacian.

1.1 The Handshaking Lemma#

Leonhard Euler initiated graph theory in 1736 by formalizing vertex degrees.

Theorem (The Handshaking Lemma):

In every finite undirected graph G = (V, E), the sum of the degrees of all vertices is equal to exactly twice the total number of edges:

Σ_{v ∈ V} deg(v) = 2 · |E|

Proof: Every undirected edge e = (u, v) has exactly two endpoints. Therefore, when summing degrees across all vertices, every individual edge is counted exactly twice: once at vertex u and once at vertex v.

Fundamental Corollary:

In any finite undirected graph, the number of vertices having an odd degree must be strictly even!

Proof: Split the degree sum into even-degree vertices and odd-degree vertices:

Σ_{v ∈ V_even} deg(v) + Σ_{v ∈ V_odd} deg(v) = 2 · |E|.

The right-hand side 2 · |E| is even. The sum of even numbers is even. Therefore, the sum of odd degrees Σ_{v ∈ V_odd} deg(v) must be even. A sum of odd integers is even if and only if there is an even number of terms.

1.2 Eulerian Paths vs. Hamiltonian Cycles#

A foundational distinction in computational complexity is between Eulerian trails and Hamiltonian cycles:

• Eulerian Trail: A continuous path that visits every single edge e ∈ E exactly once.

- Euler's Theorem (1736): A connected undirected graph contains an Eulerian trail if and only if it has exactly 0 or 2 vertices of odd degree. (If exactly 0 odd vertices, it contains an Eulerian Circuit returning to the start).

- Complexity: Can be found in linear time O(|V| + |E|) using Hierholzer's Algorithm.

• Hamiltonian Cycle: A closed cycle that visits every single vertex v ∈ V exactly once.

- Complexity: Determining whether an arbitrary graph contains a Hamiltonian cycle is NP-complete (one of Richard Karp's 21 NP-complete problems). There exists no known polynomial-time algorithm!

2. Planar Graphs & Kuratowski's Theorem#

A graph is Planar if it can be drawn (embedded) in the 2-dimensional Euclidean plane such that no two edges intersect or cross each other except at their common endpoints.

+-----------------------------------------------------------------------------+
|                  PLANAR EMBEDDING VS. NON-PLANAR CROSSING                   |
+-----------------------------------------------------------------------------+
    Planar Embedding of K_4:                Non-Planar Complete Bipartite K_3,3:
         (1)-------(2)                               (A)   (B)   (C)
          | \     / |                                  \   / \   /
          |   (4)   |                                   \ /   \ /
          | /     \ |                                    X     X
         (3)-------(0)                                  / \   /                                                       (1)   (2)   (3)
    Edges connect without crossing.        Edges MUST cross! (Utility Graph).
+-----------------------------------------------------------------------------+

2.1 Euler's Planar Characteristic Formula#

For any connected planar graph embedded in the plane with V vertices, E edges, and F distinct faces (including the single unbounded exterior face):

V - E + F = 2

Proof by Edge Induction:

• Base Case: A tree has E = V - 1 edges and F = 1 single face. V - (V - 1) + 1 = 2.
• Inductive Step: Adding an edge between existing vertices creates a cycle, dividing an existing face into two faces (E → E + 1, F → F + 1). The quantity V - E + F is strictly invariant: V - (E + 1) + (F + 1) = V - E + F = 2.

2.2 Maximum Edge Bounds for Planar Graphs#

In any planar graph where every face is bounded by at least 3 edges (2E ≥ 3F):

Substituting F ≤ (2/3) · E into Euler's formula:

V - E + (2/3) · E ≥ 2  ==>  V - (1/3) · E ≥ 2  ==>  E ≤ 3V - 6

Every simple planar graph with V ≥ 3 vertices has at most `3V - 6` edges. Planar graphs are strictly sparse!

2.3 Kuratowski's Theorem (1930)#

Kazimierz Kuratowski established the definitive characterization of planarity:

> Theorem: A finite graph is planar if and only if it does not contain a subgraph that is homeomorphic to (or can be formed by edge subdivisions of):

> 1. K_5: The complete graph on 5 vertices.

> 2. K_{3,3}: The complete bipartite "three utilities" graph with 3 vertices in each partition.

Engineering Application (VLSI Microchip Circuit Design):

In semiconductor fabrication, circuit traces printed on a single physical silicon layer cannot cross without causing electrical short circuits. Kuratowski's theorem determines whether a circuit netlist can be fabricated on a single layer, or whether engineers must add expensive multi-layer metal vias to route crossing connections.

3. Spectral Graph Theory & The Graph Laplacian#

Spectral graph theory analyzes the structural, clustering, and connectivity properties of a graph through the eigenvalues and eigenvectors of its associated matrices.

Let G = (V, E) be an undirected graph with n vertices:

1. Adjacency Matrix A: An n × n symmetric matrix where A_{ij} = 1 if (v_i, v_j) ∈ E, and 0 otherwise.
2. Degree Matrix D: An n × n diagonal matrix where D_{ii} = deg(v_i).

3.1 The Graph Laplacian Matrix (L)#

The Graph Laplacian is defined as:

L = D - A

Component-wise:

L_{ij} = deg(v_i)     if i == j
L_{ij} = -1           if i ≠ j and (v_i, v_j) ∈ E
L_{ij} = 0            otherwise

+-----------------------------------------------------------------------------+
|             THE GRAPH LAPLACIAN AS A DISCRETE DIFFERENCE OPERATOR           |
+-----------------------------------------------------------------------------+
  For any real-valued potential vector x = (x_1, x_2, ..., x_n)^T:

             x^T · L · x = Σ_{(u, v) ∈ E} (x_u - x_v)^2

  This quadratic form measures the total "smoothness" or "energy" across edges.
+-----------------------------------------------------------------------------+

3.2 Fundamental Spectral Invariants#

1. Positive Semi-Definite: Because x^T · L · x = Σ (x_u - x_v)^2 ≥ 0 for all vectors x, L is positive semi-definite.

All n eigenvalues are real, non-negative, and can be ordered:

```text

0 = λ_0 ≤ λ_1 ≤ λ_2 ≤ ... ≤ λ_{n-1}

```

1. The Zero Eigenvalue (λ_0 = 0):

The constant vector 1 = (1, 1, ..., 1)^T satisfies L · 1 = 0 · 1 = 0 (since the sum of each row in L is deg(v_i) - deg(v_i) = 0). Thus, 0 is always an eigenvalue.

1. Multiplicity of Zero Equals Connected Components:

The algebraic multiplicity of the eigenvalue 0 is strictly equal to the exact number of connected components in G!

If λ_0 = 0 and λ_1 > 0, the graph is connected. If λ_0 = λ_1 = 0, the graph consists of at least two completely disconnected subnets!

1. The Fiedler Value & Algebraic Connectivity (λ_1):

Miroslav Fiedler (1973) proved that the second smallest eigenvalue λ_1 quantifies Algebraic Connectivity: how difficult it is to partition or sever the graph. The corresponding eigenvector—the Fiedler Vector—provides the optimal continuous relaxation to the NP-hard minimum graph bisection problem (Spectral Clustering in machine learning and distributed partitioning).

4. The Max-Flow Min-Cut Theorem & Edmonds-Karp#

In a directed Flow Network G = (V, E) with non-negative edge capacities c: E → R^+, a designated Source s, and a Sink t:

• Capacity Constraint: For all edges (u, v) ∈ E, the flow satisfies 0 ≤ f(u, v) ≤ c(u, v).
• Flow Conservation: For every vertex v other than s and t, total incoming flow equals total outgoing flow:

```text

Σ_{u} f(u, v) = Σ_{w} f(v, w)

```

An s-t Cut (S, T) is a partition of V into two disjoint subsets such that s ∈ S and t ∈ T. The capacity of the cut is the sum of capacities of edges pointing from S to T:

c(S, T) = Σ_{u ∈ S, v ∈ T} c(u, v)

+-----------------------------------------------------------------------------+
|                     MAX-FLOW MIN-CUT DUALITY THEOREM                        |
+-----------------------------------------------------------------------------+
  L.R. Ford & D.R. Fulkerson (1956):

  In any network, the maximum value of an s-t flow is strictly equal to
  the minimum capacity among all valid s-t cuts:

                     Max Flow |f|  =  Min Cut c(S, T)
+-----------------------------------------------------------------------------+

4.1 The Edmonds-Karp Algorithm#

The classic Ford-Fulkerson method searches for augmenting paths in the residual graph G_f. If augmenting paths are chosen arbitrarily, Ford-Fulkerson can take exponential time or, in networks with irrational capacities, run in an infinite loop without converging to the maximum flow!

Jack Edmonds and Richard Karp (1972) proved that choosing the shortest augmenting path using Breadth-First Search (BFS) guarantees polynomial convergence:

• In each augmentation, the shortest path distance from s to any vertex v in the residual graph never decreases.
• Each edge can become critical (saturated) at most |V| / 2 times.
• Total augmenting iterations are bounded by O(|V| · |E|).
• Because each BFS takes O(|E|) time, total runtime is strictly:

```text

O(|V| · |E|^2)

```

5. Common Pitfalls & Developer Misconceptions#

Pitfall 1: Confusing Flow Capacity with Net Flow in Cut Calculations#

When calculating the capacity of an s-t cut (S, T), developers often accidentally include edges pointing backward from T to S.

Mathematical Rule: Cut capacity `c(S, T)` counts ONLY forward edges pointing from S to T! Backward edges pointing from T to S contribute zero to capacity.

Pitfall 2: Assuming Planarity Implies 2-Colorability (Bipartiteness)#

Planarity means edges can be drawn without crossings; bipartiteness means the graph has no odd-length cycles. A triangle K_3 is fully planar (V=3, E=3, F=2), but requires 3 colors and is not bipartite! By the Four Color Theorem (Appel & Haken 1976), all planar graphs are 4-colorable, but not necessarily 2-colorable.

Pitfall 3: The Handshaking Sum Edge-Case in Directed Graphs#

In directed graphs, Σ deg^+(v) = Σ deg^-(v) = |E| (total out-degrees equals total in-degrees equals total edges). Applying the undirected Handshaking lemma Σ deg(v) = 2|E| to a directed graph without distinguishing in-degree from out-degree causes off-by-two errors in network density algorithms.

6. Summary & Checkpoint Exercises#

Conceptual Summary#

1. Handshaking Lemma: Edge endpoint counting mandates that the number of odd-degree vertices is strictly even.
2. Euler's Formula & Planarity: V - E + F = 2 constrains simple planar edges to E ≤ 3V - 6; Kuratowski forbids K_5 and K_{3,3} minors.
3. Graph Laplacian: L = D - A captures algebraic connectivity λ_1 and connected component counts via zero-eigenvalue multiplicity.
4. Max-Flow Min-Cut: Maximum network throughput is mathematically identical to the bottleneck cut capacity, solvable in O(V · E^2) via Edmonds-Karp.

Practice Problems & Detailed Solutions#

Problem 1 (Proving Non-Planarity of K_{3,3} via Euler's Formula):

The complete bipartite graph K_{3,3} consists of 6 vertices partitioned into two sets of 3 vertices, with an edge connecting every vertex in the first set to every vertex in the second set (|V| = 6, |E| = 9).

Use Euler's Planar Formula to prove that K_{3,3} is non-planar.

Solution:

1. Bipartite Face Boundary Property:

In any bipartite graph, there are no odd-length cycles. Therefore, every cycle has length at least 4.

Consequently, every face in a planar embedding of a bipartite graph must be bounded by at least 4 edges:

2 · |E| ≥ 4 · F ==> F ≤ |E| / 2.

1. Substitute into Euler's Formula:

If K_{3,3} were planar, it must satisfy:

V - E + F = 2.

Substitute F ≤ |E| / 2:

V - E + (|E| / 2) ≥ 2 ==> V - (|E| / 2) ≥ 2 ==> |E| ≤ 2V - 4.

1. Evaluate for K_{3,3}:

- |V| = 6

- |E| = 9

- Test condition: 9 ≤ 2(6) - 4 = 12 - 4 = 8.

- 9 ≤ 8 is a direct mathematical contradiction!

- Conclusion: `K_{3,3}` cannot be planar.

Problem 2 (Computing the Graph Laplacian and Fiedler Vector for a Computer Network):

Consider a linear 3-server pipeline network: Server 1 is connected to Server 2, and Server 2 is connected to Server 3 (Edges = {(1, 2), (2, 3)}).

1. Construct the Adjacency Matrix A, Degree Matrix D, and Graph Laplacian L.
2. Compute the eigenvalues and verify that λ_0 = 0.
3. Identify the Fiedler Vector associated with λ_1.

Solution:

1. Matrix Construction:

- Adjacency Matrix A:

```text

A = [ 0 1 0 ]

[ 1 0 1 ]

[ 0 1 0 ]

```

- Degree Matrix D: deg(1) = 1, deg(2) = 2, deg(3) = 1.

```text

D = [ 1 0 0 ]

[ 0 2 0 ]

[ 0 0 1 ]

```

- Laplacian L = D - A:

```text

L = [ 1 -1 0 ]

[ -1 2 -1 ]

[ 0 -1 1 ]

```

1. Eigenvalue Calculation:

Compute characteristic polynomial det(L - λ · I) = 0:

```text

det [ 1-λ -1 0 ]

[ -1 2-λ -1 ] = 0

[ 0 -1 1-λ ]

= (1 - λ) · [ (2 - λ)(1 - λ) - 1 ] - (-1) · [ -1 · (1 - λ) - 0 ]

= (1 - λ) · [ λ^2 - 3λ + 1 ] - (1 - λ)

= (1 - λ) · [ λ^2 - 3λ + 1 - 1 ]

= (1 - λ) · λ · (λ - 3) = 0

```

The eigenvalues are:

λ_0 = 0, λ_1 = 1, λ_2 = 3.

Holds: λ_0 = 0 is the smallest eigenvalue!

1. Fiedler Vector for λ_1 = 1:

Solve (L - 1 · I) · v = 0:

```text

[ 0 -1 0 ] [ x ] [ 0 ]

[ -1 1 -1 ] [ y ] = [ 0 ]

[ 0 -1 0 ] [ z ] [ 0 ]

```

- From row 1: -y = 0 ==> y = 0.

- From row 2: -x + y - z = 0 ==> -x - z = 0 ==> z = -x.

- Normalizing yields the Fiedler Vector:

v_1 = (1, 0, -1)^T.

- Interpretation: The Fiedler vector assigns positive sign to Server 1 (+1) and negative sign to Server 3 (-1), with Server 2 at the boundary (0). This reveals that severing the network separates Server 1 from Server 3!

Problem 3 (Calculating Maximum Flow and Bottleneck Cut via Edmonds-Karp):

A network has vertices {s, A, B, t} with capacities:

• c(s, A) = 10
• c(s, B) = 10
• c(A, B) = 1
• c(A, t) = 10
• c(B, t) = 10
• Compute the maximum flow from s to t.
• Identify the bottleneck minimum cut (S, T) and verify that Max Flow == Min Cut Capacity.

Solution:

1. Compute Max Flow:

- Path 1: s → A → t with capacity min(10, 10) = 10.

Send 10 units. Edge (s, A) and (A, t) become saturated.

- Path 2: s → B → t with capacity min(10, 10) = 10.

Send 10 units. Edge (s, B) and (B, t) become saturated.

- No further augmenting paths exist in the residual network.

- Total Max Flow: 10 + 10 = 20.

1. Identify Min Cut (S, T):

- Partition S = {s}, T = {A, B, t}.

- Forward edges crossing the cut from S to T:

c(s, A) = 10, c(s, B) = 10.

- Cut capacity: c(S, T) = 10 + 10 = 20.

- Duality verification: Max Flow (20) == Min Cut Capacity (20). The duality theorem holds!

Problem 4 (Detecting Disconnected Subnets via Laplacian Eigenvalue Multiplicity):

An automated datacenter topology health scanner computes the Graph Laplacian matrix L for a cluster of 500 servers. The scanner computes the eigenvalue spectrum and finds:

• λ_0 = 0.0000
• λ_1 = 0.0000
• λ_2 = 0.0000
• λ_3 = 0.4521

Explain what physical network condition this spectrum indicates, and calculate how many completely severed, isolated subnets exist in the datacenter.

Solution:

1. Spectral Invariant Principle:

By the fundamental theorem of spectral graph theory, the algebraic multiplicity of the eigenvalue 0 in the Graph Laplacian matrix L is strictly equal to the exact number of connected components in the graph.

1. Evaluation:

- The eigenvalue 0 appears exactly 3 times (λ_0 = 0, λ_1 = 0, λ_2 = 0).

- The next eigenvalue is positive: λ_3 = 0.4521 > 0.

1. Physical Diagnosis:

- The datacenter network has suffered a network partition: it is severed into exactly 3 completely isolated, disconnected subnet partitions.

- No packets can travel between servers across these three components!