Graphs: Basic Concepts and Theorems

Graph Theory: Foundations

Definition and Types

Graph G = (V, E): V is the set of vertices, E is the set of edges (pairs of vertices).

Directed (digraph): edges are directed. Weighted: edges have weights.

Degree of a vertex deg(v) — the number of edges incident to v. Handshaking Lemma: Σ deg(v) = 2|E| (each edge contributes 2 to the sum of degrees). Corollary: the number of vertices of odd degree is even.

Paths and Connectivity

Walk: a sequence of vertices v₀, v₁, ..., vₖ with edges v_{i-1}v_i. Path: a walk with no repeated vertices.

A graph is connected if between any two vertices there is a path.

Connected components are maximal connected subgraphs.

Shortest paths: Dijkstra's algorithm (non-negative weights) O((V+E)log V); Bellman–Ford (allows negatives) O(VE); Floyd–Warshall (all pairs) O(V³).

Trees

Tree — a connected graph without cycles. Equivalent conditions (for n vertices):

• n−1 edges
• Any two vertices are connected by a unique path
• Connected and adding any edge creates a cycle

Spanning tree of a connected graph — a tree subgraph containing all vertices. Minimum spanning tree (MST): Kruskal's algorithm (E log E) or Prim's algorithm (E log V).

Kirchhoff Numbers

Laplacian matrix: L = D − A (D is the diagonal degree matrix, A is the adjacency matrix).

The number of spanning trees = any cofactor of L (Kirchhoff's theorem). A beautiful result linking the topology of a graph with the spectrum of its matrix.

Spectral Graph Theory

Adjacency matrix A and Laplacian L = D − A connect the structure of the graph to algebra. Eigenvalues of the Laplacian 0 = λ₁ ≤ λ₂ ≤ ... ≤ λₙ contain rich structural information. λ₂ > 0 if and only if the graph is connected. λ₂ is algebraic connectivity (Fiedler connectivity): the larger λ₂, the "more connected" the graph. Partitioning via the Fiedler vector (corresponding to λ₂) is the basis of spectral clustering in machine learning.

Kirchhoff's Matrix-Tree Theorem: The number of spanning trees τ(G) = (1/n)λ₂λ₃...λₙ (the product of the nonzero eigenvalues of L). For the complete graph Kₙ: all nonzero eigenvalues of L equal n, so τ(Kₙ) = nⁿ⁻². This is Cayley's formula (1889), proven algebraically 80 years later.

Graph Algorithms: Practice

Depth-First Search (DFS): Recursive traversal, builds a DFS tree. Complexity O(V+E). Applications: topological sorting of a DAG, finding strongly connected components (Tarjan's, Kosaraju's algorithm), checking bipartiteness, finding bridges and articulation points.

Breadth-First Search (BFS): Level-order traversal, shortest paths in an unweighted graph O(V+E). In weighted graphs with nonnegative weights — Dijkstra's algorithm O((V+E)log V) with a priority queue (Fibonacci heap gives O(E + V log V)).

MST Algorithms: Kruskal's algorithm sorts edges by weight and greedily adds without creating a cycle — O(E log E). Prim's algorithm grows the tree from an arbitrary vertex — O(E log V) with a binary heap. Correctness of both is based on the cut property: for any cut (S, VS) [vertex subset split], the minimum-weight edge crossing the cut enters the MST.

Graph Theory Problems in Computer Science

Connectivity and flows are used in network design: how to find the minimal network cut (the minimum capacity for failure), where to place redundant channels. Menger's Theorem: the minimum vertex cut = the maximum number of pairwise vertex-disjoint paths — this is the min-cut/max-flow duality in vertex formulation.

Graphs are used in compilers: control flow graph, interference graph in register allocation (coloring = register assignment), data dependency graph for parallelization. The NP-completeness of graph coloring explains why optimal register allocation is NP-hard in the general case (modern compilers use heuristics).

Planarity: Planarity Algorithm and Euler’s Formula

Euler's formula for a connected planar graph: V − E + F = 2 (V vertices, E edges, F faces including the outer one). For multiconnected: V − E + F = 1 + C (C connected components). Corollary: E ≤ 3V − 6. For bipartite planar: E ≤ 2V − 4 (no triangles). Therefore, K₅ and K_{3,3} are nonplanar: K₅ has E=10, 3V−6=9; K_{3,3} has E=9, 2V−4=8.

Kuratowski’s Theorem: A graph is planar ↔ it does not contain a subdivision of K₅ or K_{3,3}. Planarity checking algorithm in O(V): Hopcroft-Tarjan algorithm (1974) based on DFS with ST-numbering. In practice: for V < 10⁶ vertices — fast.

Hypergraphs and Their Applications

Hypergraph H = (V, E), where E ⊆ 2^V (edges are arbitrary subsets of vertices). Bipartite graph is a bipartite representation of a hypergraph (vertices ↔ graph vertices, edges ↔ “edge” vertices). Hypergraphs model multi-way relationships: employees ↔ projects, genes ↔ diseases, terms ↔ documents.

Hypergraph coloring (Property B): A hypergraph is 2-colorable if its vertices can be colored in 2 colors so that no edge is monochromatic. Not all hypergraphs are 2-colorable — Erdős’s probabilistic method yields a condition: if each edge contains ≥ k vertices and each vertex is in ≤ 2^{k−2} edges, then 2-colorable. Used in load balancing and game theory.

Numerical Example: Dijkstra’s Algorithm

Problem: Find the shortest paths from A in the graph: A−B:4, A−C:2, C−B:1, B−D:5, C−D:8.

Step 1: Initialization: d(A)=0, d(B)=∞, d(C)=∞, d(D)=∞. Priority queue: {A}.

Step 2: Extract A (d=0). Update neighbors: d(B)←min(∞,0+4)=4; d(C)←min(∞,0+2)=2.

Step 3: Extract C (d=2). Update: d(B)←min(4,2+1)=3; d(D)←min(∞,2+8)=10.

Step 4: Extract B (d=3). Update: d(D)←min(10,3+5)=8. Extract D (d=8). Done.

Result: d(A→B)=3 (path A→C→B), d(A→C)=2, d(A→D)=8 (path A→C→B→D). All shortest paths from A are found: lengths 2, 3, 8. These are distances, not flows — Dijkstra's algorithm solves the shortest path problem, not maximum flow.