What is the Handshaking Lemma in graph theory?

The Handshaking Lemma states that in any graph, the sum of all vertex degrees equals twice the number of edges. Formally, the sum of deg(v) over all vertices v equals 2|E|. This follows because every edge contributes exactly 1 to the degree of each of its two endpoints, so it is counted twice in the total degree sum. An immediate corollary is that every graph has an even number of odd-degree vertices.

What is the difference between an Eulerian circuit and a Hamiltonian cycle?

An Eulerian circuit traverses every edge exactly once and returns to the starting vertex. By Euler's theorem, a connected graph has an Eulerian circuit if and only if every vertex has even degree. A Hamiltonian cycle visits every vertex exactly once and returns to the start. There is no simple characterization of Hamiltonian graphs — determining whether a Hamiltonian cycle exists is NP-complete in general. Dirac's theorem gives a sufficient condition: if every vertex has degree at least n/2 in an n-vertex graph, a Hamiltonian cycle exists.

What does Euler's formula V - E + F = 2 mean for planar graphs?

Euler's formula for connected planar graphs states that V - E + F = 2, where V is the number of vertices, E the number of edges, and F the number of faces (including the unbounded outer face). This formula has powerful consequences: every simple planar graph satisfies E at most 3V - 6, and if the graph is triangle-free then E at most 2V - 4. These inequalities are used to prove that K5 and K3,3 are non-planar, which by Kuratowski's theorem characterizes all non-planar graphs.

What is Hall's Marriage Theorem?

Hall's Marriage Theorem gives a necessary and sufficient condition for a perfect matching in a bipartite graph. Let G be a bipartite graph with parts X and Y. A matching that saturates all vertices of X exists if and only if for every subset S of X, the neighborhood N(S) satisfies |N(S)| at least |S|. This condition is called Hall's condition. The theorem is used to prove the existence of systems of distinct representatives and is foundational in combinatorics and optimization.

What is the Max-Flow Min-Cut Theorem?

The Max-Flow Min-Cut Theorem states that in a flow network, the maximum value of a flow from source s to sink t equals the minimum capacity of an s-t cut. An s-t cut partitions the vertices into two sets S containing s and T containing t, and its capacity is the total capacity of edges going from S to T. This duality connects a combinatorial optimization problem (maximum flow) with a structural property of the network (minimum cut), and it implies König's theorem and Hall's theorem as special cases.

What is the chromatic polynomial of a graph?

The chromatic polynomial P(G, k) counts the number of proper k-colorings of graph G, where no two adjacent vertices share the same color. It is indeed a polynomial in k. For a tree on n vertices, P(T, k) = k(k-1)^(n-1). For a cycle Cn, P(Cn, k) = (k-1)^n + (-1)^n (k-1). The chromatic number chi(G) is the smallest positive integer k for which P(G, k) is positive. The deletion-contraction recurrence P(G, k) = P(G - e, k) - P(G / e, k) allows recursive computation.

How does Tarjan's algorithm find strongly connected components?

Tarjan's algorithm finds all strongly connected components (SCCs) of a directed graph in linear O(V + E) time using a single depth-first search. Each vertex is assigned a discovery time and a low-link value representing the smallest discovery time reachable from its subtree. Vertices are pushed onto a stack during DFS. When a vertex v has low[v] equal to its discovery time, it is the root of an SCC, and the algorithm pops the stack down to v, collecting all vertices of that SCC. The algorithm processes each SCC in reverse topological order of the condensation DAG.

Advanced Mathematics

Graph Theory: The Mathematics of Networks

Graph theory studies structures made of vertices connected by edges. From the Königsberg bridge problem that launched the field in 1736 to modern algorithms powering the internet, social networks, and GPS routing, graphs are one of mathematics' most versatile and practically important tools.

1. Basic Definitions and Terminology

A graph G consists of a vertex set V and an edge set E, written G = (V, E). Edges represent pairwise relationships between vertices. This simple abstraction captures an enormous variety of real-world structures.

Vertices and Edges

Each edge connects two vertices, called its endpoints. In an undirected graph, an edge between u and v is the unordered pair of u and v. A loop is an edge from a vertex to itself. Multiple edges between the same pair of vertices are called parallel edges or multi-edges.

Core terminology:

Order of G: |V|, the number of vertices
Size of G: |E|, the number of edges
Adjacent vertices: connected by at least one edge
Incident: a vertex and an edge sharing an endpoint
Neighborhood N(v): all vertices adjacent to v
Degree deg(v): number of edges incident to v (loops count twice)

Types of Graphs

Type	Description	Example Use
Simple graph	No loops or parallel edges	Friendship networks
Multigraph	Allows parallel edges	Airline routes (multiple flights)
Directed graph (digraph)	Edges have orientation (arcs)	Web page links, citations
Weighted graph	Edges carry numerical values	Road distances, costs
Bipartite graph	Vertices split into two independent sets	Job assignment, matching
Complete graph Kn	Every pair of vertices connected	Tournament scheduling

The Handshaking Lemma

One of the most fundamental results in graph theory is the Handshaking Lemma, attributed to Euler: in any graph, the sum of all vertex degrees equals twice the number of edges.

Sum of deg(v) over all v in V = 2 times |E|

Proof: each edge uv contributes 1 to deg(u) and 1 to deg(v), so it is counted exactly twice in the total degree sum.

Corollary: every graph has an even number of odd-degree vertices.

For the complete graph Kn: each vertex has degree n-1, so the total degree sum is n(n-1), and the number of edges is n(n-1)/2.

Degree Sequences and the Erdos-Gallai Theorem

The degree sequence of a graph lists all vertex degrees in non-increasing order. The Erdos-Gallai theorem characterizes which sequences are graphical (realizable as the degree sequence of a simple graph): a non-increasing sequence d1, d2, ..., dn is graphical if and only if the sum of all di is even and for each k from 1 to n, the sum of the first k terms is at most k(k-1) plus the sum over i from k+1 to n of min(di, k). The Havel-Hakimi algorithm provides an efficient constructive test.

2. Trees and Spanning Trees

A tree is a connected acyclic graph. Trees are among the most important graph structures in computer science and combinatorics, appearing in data structures, algorithms, phylogenetics, and network design.

Characterizations of Trees

For a graph G on n vertices, the following statements are equivalent:

(1) G is a tree (connected and acyclic)
(2) G is connected and has exactly n-1 edges
(3) G is acyclic and has exactly n-1 edges
(4) Any two vertices are connected by exactly one path
(5) G is minimally connected: removing any edge disconnects it
(6) G is maximally acyclic: adding any edge creates exactly one cycle

Cayley's Formula

The number of labeled trees on n vertices is n raised to the power n-2. This remarkable formula, proved by Arthur Cayley in 1889, says for example that there are 16 labeled trees on 4 vertices (4 squared) and 125 labeled trees on 5 vertices (5 cubed). The formula is proved via the Prüfer sequence bijection.

Prüfer Sequences

The Prüfer sequence provides a bijection between labeled trees on n vertices and sequences of length n-2 with entries from 1 to n. To encode a tree:

Encoding algorithm:

Find the leaf with the smallest label
Record the label of its unique neighbor
Delete that leaf from the tree
Repeat until two vertices remain

The resulting sequence has length n-2. Decoding reconstructs the unique tree from any sequence, establishing the bijection and proving Cayley's formula.

Kirchhoff's Matrix-Tree Theorem

The number of spanning trees of a graph G equals any cofactor of the Laplacian matrix L = D - A, where D is the diagonal degree matrix and A is the adjacency matrix. Equivalently, if the eigenvalues of L are 0 = lambda1 less than or equal to lambda2 less than or equal to ... less than or equal to lambdan, then the number of spanning trees equals (1/n) times the product lambda2 times lambda3 times ... times lambdan.

Minimum Spanning Trees

Given a weighted connected graph, a minimum spanning tree (MST) is a spanning tree with minimum total edge weight. Two classical greedy algorithms find MSTs efficiently:

Kruskal's Algorithm

Sort all edges by weight
Greedily add the cheapest edge that does not create a cycle
Use Union-Find for cycle detection
Time: O(E log E)

Prim's Algorithm

Start from any vertex
Repeatedly add cheapest edge leaving current tree
Use a priority queue
Time: O(E log V) with binary heap

Both algorithms are correct by the Cut Property: if e is the minimum weight edge crossing some cut of the graph, then e belongs to every MST.

3. Connectivity

Connectivity measures how well a graph holds together when vertices or edges are removed. It is critical in network reliability, fault tolerance, and the design of robust communication systems.

Cut Vertices and Bridges

A cut vertex (articulation point) is a vertex whose removal disconnects the graph. A bridge is an edge whose removal disconnects the graph. Both can be found in linear time O(V + E) using depth-first search and tracking discovery times and low-link values.

Detection criterion (DFS-based):

The root of the DFS tree is a cut vertex iff it has 2 or more children in the DFS tree
A non-root vertex u is a cut vertex iff it has a child v with low[v] at least disc[u]
An edge (u, v) is a bridge iff low[v] is greater than disc[u]
Here disc[u] is the discovery time and low[u] is the minimum discovery time reachable via the DFS subtree of u

2-Connected Graphs and Blocks

A graph is 2-connected if it has no cut vertices and at least 3 vertices. Equivalently, there are two internally vertex-disjoint paths between any two vertices. A block is a maximal 2-connected subgraph (or a bridge with its endpoints, or an isolated vertex). The block-cut tree of a graph represents the block structure: it is a tree with nodes for blocks and cut vertices, with an edge whenever a cut vertex belongs to a block.

k-Connectivity and Menger's Theorem

The vertex connectivity kappa(G) is the minimum number of vertices whose removal disconnects G (or makes it trivial). The edge connectivity lambda(G) is the minimum number of edges whose removal disconnects G. For any graph, kappa(G) is at most lambda(G) which is at most delta(G), where delta(G) is the minimum degree.

Menger's Theorem (1927):

The maximum number of internally vertex-disjoint paths from s to t equals the minimum number of vertices whose removal separates s from t.

Edge version: the maximum number of edge-disjoint paths from s to t equals the minimum number of edges in an s-t cut.

Menger's theorem is a min-max duality result; it follows from the max-flow min-cut theorem when edge capacities are all 1.

Whitney's Theorem and 3-Connectivity

Whitney proved that a graph is 2-connected if and only if any two vertices are connected by at least 2 internally vertex-disjoint paths. For 3-connectivity, Tutte characterized 3-connected graphs as those obtained from K4 by a sequence of vertex splits (the converse of edge contractions), giving a recursive structure theorem.

4. Eulerian and Hamiltonian Graphs

Two classical traversal problems ask about walks that use every edge exactly once (Eulerian) or visit every vertex exactly once (Hamiltonian). Despite superficial similarity, these problems have very different complexity profiles.

Euler's Theorem

The Königsberg bridge problem (1736) asked whether one could walk through the city crossing each of seven bridges exactly once. Euler proved it was impossible and, in doing so, founded graph theory. His criterion:

Eulerian circuit: A connected graph has an Eulerian circuit iff every vertex has even degree.
Eulerian path: A connected graph has an Eulerian path (not a circuit) iff it has exactly two odd-degree vertices; the path starts and ends at these vertices.
For digraphs: An Eulerian circuit exists iff the graph is strongly connected and every vertex has equal in-degree and out-degree.

Hierholzer's Algorithm

Hierholzer's algorithm constructs an Eulerian circuit in O(E) time. Starting from any vertex, it follows edges (marking them used) until returning to the start, forming a cycle. If unused edges remain, it finds a vertex on the current circuit incident to an unused edge, builds a new cycle from there, and splices the two cycles together. The process repeats until all edges are used.

Hamiltonian Graphs

A Hamiltonian cycle visits every vertex exactly once. Unlike Eulerian graphs, there is no simple characterization. Determining whether a Hamiltonian cycle exists is NP-complete (one of Karp's 21 NP-complete problems). However, several sufficient conditions are known:

Dirac's Theorem (1952): If G is a simple graph on n vertices with n at least 3 and every vertex has degree at least n/2, then G is Hamiltonian.
Ore's Theorem (1960): If for every pair of non-adjacent vertices u, v we have deg(u) + deg(v) at least n, then G is Hamiltonian.
Chvátal's Theorem: A comprehensive closure-based condition that implies both Dirac and Ore as special cases.

Travelling Salesman Problem (TSP)

TSP asks for the shortest Hamiltonian cycle in a weighted complete graph. It is NP-hard in general. For metric instances (satisfying the triangle inequality), approximation algorithms exist: the 2-approximation via MST (double the MST and shortcut), and Christofides' 3/2-approximation using MST plus minimum weight perfect matching on odd-degree vertices. In 2020, a (3/2 - epsilon) approximation was announced for general metric TSP.

5. Graph Coloring

A proper vertex coloring assigns colors to vertices so no two adjacent vertices share a color. The chromatic number chi(G) is the minimum number of colors needed. Graph coloring models scheduling, register allocation, frequency assignment, and map coloring problems.

Greedy Coloring and Upper Bounds

The greedy algorithm colors vertices one by one, assigning the smallest available color not used by any already-colored neighbor. It uses at most Delta + 1 colors, where Delta is the maximum degree. The order of processing affects the number of colors used; finding the optimal ordering is NP-hard in general.

Key bounds on chromatic number:

chi(G) is at least omega(G) (clique number lower bound)
chi(G) is at least n divided by alpha(G) (independence number bound)
chi(G) is at most Delta + 1 (greedy upper bound)
chi(G) is at most Delta (Brooks' theorem, with exceptions)

Brooks' Theorem

Brooks' theorem (1941) states that for a connected graph G that is neither a complete graph nor an odd cycle, chi(G) is at most Delta. This improves the greedy bound by 1 for most graphs. The proof constructs a special vertex ordering ensuring the greedy algorithm uses at most Delta colors.

The Four Color Theorem

The Four Color Theorem states that every planar graph is 4-colorable — equivalently, every map can be colored with four colors so no two adjacent regions share a color. Conjectured in 1852, it was proved by Appel and Haken in 1976 using extensive computer assistance to check 1,936 unavoidable configurations. A shorter computer-assisted proof was given by Robertson, Sanders, Seymour, and Thomas in 1997. No human-readable proof is known.

Chromatic Polynomial

The chromatic polynomial P(G, k) counts the number of proper k-colorings of G. It satisfies the deletion-contraction recurrence: P(G, k) = P(G minus e, k) minus P(G slash e, k), where G minus e is G with edge e deleted and G slash e is G with e contracted.

Chromatic polynomials of common graphs:

Empty graph on n vertices: k raised to n
Complete graph Kn: k times (k-1) times (k-2) times ... times (k-n+1)
Tree on n vertices: k times (k-1) raised to n-1
Cycle Cn: (k-1) raised to n, plus (-1) raised to n, times (k-1)
Path Pn: k times (k-1) raised to n-1

Edge Coloring

An edge coloring assigns colors to edges so no two incident edges share a color. The chromatic index chi-prime(G) satisfies Delta at most chi-prime(G) at most Delta + 1 by Vizing's theorem (1964). Graphs with chi-prime(G) = Delta are Class 1; those with chi-prime(G) = Delta + 1 are Class 2. Bipartite graphs are always Class 1 by König's edge coloring theorem.

6. Planar Graphs

A graph is planar if it can be drawn in the plane with no edge crossings. Planar graphs arise in printed circuit board design, geographic maps, and routing problems where crossings are costly or impossible.

Euler's Formula

For any connected planar graph drawn in the plane, Euler's formula holds:

V - E + F = 2

where V = vertices, E = edges, F = faces (regions, including the unbounded outer face).

Proof sketch: start with a spanning tree (V vertices, V-1 edges, 1 face). Check: V - (V-1) + 1 = 2. Each edge added beyond the spanning tree splits a face into two, increasing E by 1 and F by 1, preserving V - E + F = 2.

Consequences:

Simple planar graph: E is at most 3V - 6 (since each face borders at least 3 edges)
Triangle-free planar graph: E is at most 2V - 4
Every planar graph has a vertex of degree at most 5
Every planar graph is 5-colorable (easy) and 4-colorable (hard)

Kuratowski's Theorem

Kuratowski's theorem (1930) gives a complete characterization of planar graphs: a graph is planar if and only if it contains no subdivision of K5 or K3,3 as a subgraph. A subdivision replaces edges with internally vertex-disjoint paths.

Wagner's theorem gives an equivalent statement using graph minors: a graph is planar if and only if it has no K5 or K3,3 as a minor. A minor is obtained by contracting edges, deleting edges, and deleting vertices. This formulation connects planarity to the broader Robertson-Seymour theory of graph minors.

Graph Drawing and Crossing Number

For non-planar graphs, the crossing number cr(G) is the minimum number of edge crossings in any drawing of G in the plane. Computing the crossing number is NP-hard. Known results: cr(K5) = 1, cr(K6) = 3, cr(K7) = 9. The Zarankiewicz conjecture on the crossing number of complete bipartite graphs Kr,s remains open.

Planar Graph Algorithms

Planarity testing can be done in linear O(V + E) time using algorithms by Hopcroft and Tarjan (1974) or the LR-planarity algorithm. Planar graphs admit efficient algorithms for many problems that are NP-hard on general graphs, including maximum independent set and minimum vertex cover.

7. Matching Theory

A matching in a graph is a set of edges with no shared endpoints. Matching theory addresses questions about the existence and size of matchings, with applications in assignment problems, scheduling, and network design.

Basic Definitions

Matching M: a set of pairwise non-adjacent edges
Matched vertex: a vertex incident to an edge in M
Maximum matching: a matching of maximum cardinality
Perfect matching: a matching that saturates every vertex (requires even n)
Augmenting path: a path alternating between non-matching and matching edges, with both endpoints unmatched
Berge's theorem: M is maximum iff there is no augmenting path with respect to M

Hall's Marriage Theorem

For bipartite graphs G with parts X and Y, a matching saturating all of X exists iff Hall's condition holds: for every subset S of X, the neighborhood |N(S)| is at least |S|.

Intuition: you cannot match all of X to distinct vertices in Y if some subset S has too few neighbors to accommodate all of them. Hall's theorem says this obvious necessary condition is also sufficient.

König's Theorem

König's theorem (1931) is a cornerstone of bipartite graph theory: in any bipartite graph, the maximum matching size equals the minimum vertex cover size (minimum number of vertices touching every edge). This is a min-max duality result; it follows from the max-flow min-cut theorem.

König's theorem corollaries (bipartite graphs):

Maximum independent set = n minus maximum matching
Minimum vertex cover = maximum matching
Maximum matching = n/2 iff G has a perfect matching
Edge chromatic number = Delta (Class 1 edge coloring)

Edmonds' Blossom Algorithm

For general (non-bipartite) graphs, augmenting path search is complicated by odd cycles. Edmonds' blossom algorithm (1965) handles this by identifying blossoms (odd cycles encountered during augmenting path search) and contracting them into single vertices, then searching for augmenting paths in the contracted graph. This gives an O(V cubed) algorithm for maximum matching, later improved to O(E times the square root of V) by Micali and Vazirani.

8. Network Flows

A flow network is a directed graph where each edge has a capacity and we want to send flow from a source vertex s to a sink vertex t, respecting capacity constraints and flow conservation. Network flow models commodity transport, bandwidth allocation, circulation problems, and many combinatorial optimization problems.

Flow Definitions

Capacity constraint: 0 at most f(u,v) at most c(u,v) for every edge (u,v)
Conservation: for every vertex v except s and t, inflow equals outflow
Value of flow: net flow out of s (equals net flow into t)
Residual graph: for each edge (u,v), add forward edge with residual capacity c(u,v) - f(u,v) and backward edge with capacity f(u,v)
Augmenting path: any s-t path in the residual graph (can push more flow)

Max-Flow Min-Cut Theorem

The maximum value of an s-t flow equals the minimum capacity of an s-t cut. An s-t cut separates vertices into two sets S containing s and T containing t, with capacity equal to the sum of capacities of edges from S to T (not backward edges). This theorem, proved by Ford and Fulkerson in 1956, is one of the most influential results in combinatorial optimization.

Algorithms for Maximum Flow

Algorithm	Method	Complexity
Ford-Fulkerson	Augment along any path in residual graph	O(E times max-flow value); may not terminate with irrational capacities
Edmonds-Karp	BFS augmenting paths (shortest path first)	O(V times E squared)
Dinic's	Blocking flows in layered graph	O(V squared times E); O(E times sqrt(V)) for unit capacities
Push-Relabel	Maintains preflow, relabels vertices	O(V squared times sqrt(E))

Flow Applications

Network flow is a powerful modeling tool. Many combinatorial problems reduce to flow:

Bipartite matching: add source connected to X, sink connected to Y, all capacities 1; max flow = max matching
Project selection: choose profitable projects with required tools via s-t minimum cut
Circulation with lower bounds: route flow with both lower and upper capacity bounds
Survey design: determine feasible interview plans with flow constraints
Image segmentation: find minimum-energy cuts in image graphs

9. Spectral Graph Theory

Spectral graph theory studies graphs through the eigenvalues and eigenvectors of matrices associated with them, primarily the adjacency matrix and the Laplacian. Spectral methods reveal deep connections between graph structure and linear algebra.

Adjacency Matrix Spectrum

The adjacency matrix A of a graph G on n vertices is the n-by-n matrix with A[i][j] = 1 iff vertices i and j are adjacent, and 0 otherwise. Since A is real symmetric, its eigenvalues are all real. Order them lambda1 at least lambda2 at least ... at least lambdan.

Key spectral facts:

The number of closed walks of length k equals the sum of all eigenvalues raised to k
The largest eigenvalue lambda1 satisfies: average degree at most lambda1 at most maximum degree
G is bipartite iff the spectrum is symmetric about 0 (i.e., negative lambda is an eigenvalue whenever lambda is)
The number of triangles in G equals (1/6) times the sum of eigenvalues cubed
For d-regular graphs, lambda1 = d, and the spectral gap d minus lambda2 determines expansion

The Graph Laplacian

The Laplacian matrix L = D - A, where D is the diagonal matrix of degrees. The Laplacian is positive semi-definite: all eigenvalues are non-negative. The smallest eigenvalue is always 0, with eigenvector the all-ones vector. The multiplicity of eigenvalue 0 equals the number of connected components.

Algebraic connectivity (Fiedler value):

The second-smallest eigenvalue lambda2(L), called the Fiedler value, measures how well-connected the graph is. A larger Fiedler value means higher connectivity and better expansion. The Fiedler vector (corresponding eigenvector) is used for graph partitioning and spectral clustering.

Cheeger's inequality relates the Fiedler value to the edge expansion h: h squared divided by 2 is at most lambda2 divided by 2 is at most h.

Expander Graphs

Expander graphs are sparse graphs with high connectivity — every small set of vertices has many neighbors. Formally, a family of d-regular graphs is an expander family if the second eigenvalue lambda2 of the adjacency matrix is bounded away from d by a constant. Expanders are used in error-correcting codes, derandomization, network design, and the proof of the PCP theorem. Explicit constructions include Ramanujan graphs, where lambda2 is at most 2 times the square root of d-1 (the Alon-Boppana bound).

10. Random Graphs

Random graph theory, pioneered by Erd&odblac;s and Rényi, studies graphs generated by random processes. It reveals threshold phenomena — properties that appear suddenly as a parameter crosses a critical value — and provides models for real-world networks.

The Erd&odblac;s-Rényi Models

Two standard models:

G(n, p): n labeled vertices, each potential edge included independently with probability p. The expected number of edges is p times n(n-1)/2.
G(n, m): a uniformly random graph on n vertices with exactly m edges.
These models are equivalent for most purposes when p = m divided by n(n-1)/2. Analysis of G(n,p) is often easier due to edge independence.

Phase Transitions and Thresholds

Many graph properties exhibit sharp thresholds. Setting p = c/n for constant c:

c value	Structure of G(n, c/n)
c less than 1	All components are trees or unicyclic; largest has O(log n) vertices
c = 1	Critical window: largest component has order n to the 2/3 power
c greater than 1	Giant component containing a positive fraction of vertices; all other components O(log n)
p = (ln n + c) / n	Connectivity threshold: G(n,p) is connected with high probability iff c tends to infinity

Small-World and Scale-Free Networks

Real-world networks differ from Erd&odblac;s-Rényi graphs in two key ways:

Small world (Watts-Strogatz model): high clustering coefficient (friends of friends tend to be friends) combined with small average path length. Start with a ring lattice and rewire edges with small probability p, interpolating between regular and random.
Scale-free (Barabási-Albert model): degree distribution follows a power law. Generated by preferential attachment: new vertices attach to existing vertices with probability proportional to current degree. Models the internet, citation networks, and metabolic networks.

11. Graph Algorithms

Graph algorithms are among the most important in computer science, underlying navigation, networking, scheduling, and machine learning.

BFS and DFS

Breadth-First Search (BFS)

Explores vertices layer by layer
Uses a queue (FIFO)
Finds shortest paths in unweighted graphs
Time: O(V + E)
Space: O(V)
Applications: shortest path, bipartiteness testing, broadcasting

Depth-First Search (DFS)

Explores as deep as possible before backtracking
Uses a stack (or recursion)
Builds DFS tree with discovery/finish times
Time: O(V + E)
Applications: cycle detection, topological sort, SCCs, bridges

Shortest Paths

Algorithm	Use Case	Complexity
Dijkstra	Single source, non-negative weights	O((V + E) log V) with binary heap
Bellman-Ford	Single source, negative weights; detects negative cycles	O(V times E)
Floyd-Warshall	All-pairs shortest paths	O(V cubed)
Johnson's	All-pairs, sparse graphs with negative weights	O(V times E + V squared times log V)

Topological Sort

A topological ordering of a DAG (directed acyclic graph) is a linear ordering of vertices such that for every directed edge (u, v), u appears before v. Two algorithms:

DFS-based: run DFS; output vertices in reverse order of finish times. If a back edge is found, the graph has a cycle. Time: O(V + E).
Kahn's algorithm: repeatedly remove vertices with in-degree 0 and add them to the ordering, decrementing in-degrees of their neighbors. If all vertices are removed, the ordering is valid; if not, a cycle exists. Time: O(V + E).

Strongly Connected Components

A strongly connected component (SCC) of a digraph is a maximal set of vertices such that there is a directed path between every pair. Two linear-time algorithms:

Tarjan's Algorithm

Single DFS pass
Tracks discovery time and low-link value
Uses a stack to collect SCC members
Outputs SCCs in reverse topological order
Time: O(V + E)

Kosaraju's Algorithm

Two DFS passes
First pass: DFS on G, record finish times
Second pass: DFS on transpose of G in reverse finish order
Each DFS tree in pass 2 is an SCC
Time: O(V + E)

12. Applications of Graph Theory

Graph theory is one of mathematics' most practically applied branches. Modern technology is saturated with graph problems.

Social Networks

Vertices = users; edges = friendships or follows
Community detection via graph partitioning
Influence propagation (independent cascade model)
Six degrees of separation (small-world property)
Centrality measures: degree, betweenness, PageRank

Road and Transport Networks

GPS routing via Dijkstra or A*
Traffic flow optimization via network flow
Vehicle routing (generalized TSP)
Public transit scheduling via matching
Airline hub design via facility location

Computer Science

Compiler register allocation via graph coloring
Deadlock detection via cycle detection in wait-for graphs
Dependency resolution via topological sort
Web crawling and PageRank via random walks
Circuit design: planarity testing for PCB layout

Biology and Chemistry

Protein interaction networks: vertices = proteins
Phylogenetic trees: evolutionary relationships
Metabolic pathways: directed graphs of reactions
Drug-target interaction as bipartite graphs
Brain connectivity (connectome) analysis

Scheduling Problems

Many scheduling problems reduce to graph problems. Exam scheduling reduces to graph coloring: vertices are exams, edges connect exams sharing students, and colors are time slots. Job scheduling with precedence constraints reduces to topological sort on the precedence DAG. Resource allocation often reduces to matching or flow.

The Internet and PageRank

Google's PageRank algorithm models web surfing as a random walk on the web graph. From any page, follow a random outgoing link with probability d (damping factor, typically 0.85), or jump to a random page with probability 1-d. The stationary distribution of this Markov chain is the PageRank vector, assigning higher scores to pages with many high-quality inbound links. PageRank is an eigenvector of a modified adjacency matrix (the Google matrix).

13. Practice Problems with Solutions

Work through these problems to solidify your understanding. Click each problem to reveal the solution.

Problem 1: Degree Sequence — Is (5, 4, 3, 3, 2, 2, 1) a graphical sequence?

We apply the Havel-Hakimi algorithm: repeatedly remove the highest-degree vertex and subtract 1 from the degrees of the next highest-degree vertices.

Start: (5, 4, 3, 3, 2, 2, 1). Remove the vertex of degree 5 and subtract 1 from the next 5 degrees: (4-1, 3-1, 3-1, 2-1, 2-1, 1) = (3, 2, 2, 1, 1, 1). Sort: (3, 2, 2, 1, 1, 1).

Remove degree-3 vertex, subtract 1 from next 3: (2-1, 2-1, 1-1, 1, 1) = (1, 1, 0, 1, 1). Sort: (1, 1, 1, 1, 0).

Remove degree-1 vertex, subtract 1 from next 1: (1-1, 1, 1, 0) = (0, 1, 1, 0). Sort: (1, 1, 0, 0).

Remove degree-1 vertex, subtract from next 1: (1-1, 0, 0) = (0, 0, 0). All zeros.

Yes, (5, 4, 3, 3, 2, 2, 1) is a graphical sequence. The sum of degrees is 20, which is even, consistent with 10 edges.

Problem 2: Spanning Tree Count — How many spanning trees does K4 have? Verify using Cayley's formula.

Cayley's formula: the number of labeled spanning trees of Kn is n raised to n-2.

For K4: number of spanning trees = 4 raised to 4-2 = 4 squared = 16.

Verification via Kirchhoff's matrix-tree theorem: for Kn, the Laplacian eigenvalues are 0 (multiplicity 1) and n (multiplicity n-1). For K4: eigenvalues 0, 4, 4, 4.

Number of spanning trees = (1/n) times product of non-zero eigenvalues = (1/4) times 4 times 4 times 4 = 64/4 = 16. Confirmed.

Problem 3: Euler and Hamilton — The Petersen graph has 10 vertices, 15 edges, and is 3-regular. Does it have an Eulerian circuit? A Hamiltonian cycle?

Eulerian circuit: By Euler's theorem, a connected graph has an Eulerian circuit iff every vertex has even degree. The Petersen graph is 3-regular (every vertex has degree 3, which is odd). Therefore the Petersen graph has no Eulerian circuit. It also has no Eulerian path (that would require exactly two odd-degree vertices; all 10 are odd).

Hamiltonian cycle: The Petersen graph is famously non-Hamiltonian. This can be verified by exhaustive case analysis. The Petersen graph is hypohamiltonian: removing any single vertex leaves a Hamiltonian graph, but the full graph has no Hamiltonian cycle. Its girth-5 structure with the specific crossing edges makes a Hamiltonian cycle impossible.

Problem 4: Graph Coloring — What is the chromatic number of the Petersen graph? Can it be 3-colored?

The Petersen graph contains odd cycles (it has girth 5, containing 5-cycles), so it is not bipartite, hence chi is at least 3.

To show chi = 3, we must exhibit a valid 3-coloring. Label the outer 5-cycle vertices 1,2,3,4,5 and the inner 5-cycle vertices 6,7,8,9,10, with spokes connecting i to i+5.

One valid 3-coloring: outer cycle vertices get colors A, B, A, B, C (cycle: 1-2-3-4-5-1 with colors A,B,A,B,C). Inner cycle colors are adjusted to avoid conflicts with spokes and inner edges.

The Petersen graph has chromatic number chi = 3.

Problem 5: Planar Graphs — Prove that K5 is non-planar using Euler's formula.

K5 has V = 5 vertices and E = 5 times 4 divided by 2 = 10 edges.

Suppose K5 is planar. By Euler's formula V - E + F = 2: 5 - 10 + F = 2, so F = 7.

Each face is bounded by at least 3 edges, and each edge borders exactly 2 faces. Therefore 3 times F is at most 2 times E, giving 3 times 7 = 21 is at most 2 times 10 = 20.

This is a contradiction (21 is not at most 20). Therefore K5 is not planar.

Direct inequality check: E at most 3V - 6 gives 10 at most 3(5) - 6 = 9. Since 10 is greater than 9, K5 violates the planarity inequality and is non-planar.

Problem 6: Maximum Flow — Find the max flow from s to t with edges: s to a (cap 3), s to b (cap 2), a to b (cap 1), a to t (cap 2), b to t (cap 3).

We find augmenting paths using Ford-Fulkerson.

Path 1: s to a to t. Bottleneck = min(3, 2) = 2. Send flow 2. Remaining capacity: s-a has 1, a-t is saturated.

Path 2: s to b to t. Bottleneck = min(2, 3) = 2. Send flow 2. Remaining: s-b saturated, b-t has 1 remaining.

Path 3: s to a to b to t. Capacities: s-a = 1, a-b = 1, b-t = 1. Bottleneck = 1. Send flow 1.

Total flow = 2 + 2 + 1 = 5.

Minimum cut verification: the cut separating s alone from all others has capacity 3 + 2 = 5. Since max flow = min cut = 5, the answer is confirmed.

Problem 7: Hall's Theorem — Students A, B, C can do: A can do projects 1 or 2; B can do 1 or 3; C can do 2 or 3. Can all be assigned distinct projects?

Model as bipartite graph with students X and projects Y. Check Hall's condition for all subsets S of X.

Singletons: N(A) = 2 elements, N(B) = 2, N(C) = 2. All at least 1. OK.

Pairs: N(A,B) = projects 1,2,3 = 3 elements at least 2. N(A,C) = 1,2,3 = 3 at least 2. N(B,C) = 1,2,3 = 3 at least 2. OK.

Triple: N(A,B,C) = 1,2,3 = 3 at least 3. OK.

Hall's condition is satisfied. A perfect matching exists. Valid assignments include: A gets project 2, B gets project 1, C gets project 3 (or A-1, B-3, C-2).

Problem 8: Strongly Connected Components — Find the SCCs of the digraph with edges: 1 to 2, 2 to 3, 3 to 1, 2 to 4, 4 to 5, 5 to 4, 5 to 6.

Identify cycles: 1 to 2 to 3 to 1 is a cycle, so vertices 1, 2, 3 form one SCC. Edges 4 to 5 to 4 form a cycle, so 4 and 5 form one SCC. Vertex 6 has no outgoing edge returning to any other vertex, so it is its own SCC.

SCCs: SCC1 = vertices 1, 2, 3. SCC2 = vertices 4, 5. SCC3 = vertex 6.

The condensation DAG has three nodes with directed edges SCC1 to SCC2 (via edge 2 to 4) and SCC2 to SCC3 (via edge 5 to 6). Topological order: SCC1, then SCC2, then SCC3.

Quick Reference: Key Theorems

Theorem	Statement (informal)	Key Condition
Handshaking Lemma	Sum of degrees = 2 times \|E\|	Any graph
Euler's Circuit Theorem	Eulerian circuit exists iff all degrees even	Connected graph
Dirac's Theorem	min degree at least n/2 implies Hamiltonian	Simple graph, n at least 3
Euler's Planar Formula	V - E + F = 2	Connected planar graph
Kuratowski's Theorem	Planar iff no K5 or K3,3 subdivision	Any graph
Four Color Theorem	Every planar graph is 4-colorable	Planar graph
Brooks' Theorem	chi(G) at most Delta, with exceptions	Not Kn or odd cycle
Hall's Theorem	Perfect matching exists iff Hall's condition holds	Bipartite graph
König's Theorem	Max matching = min vertex cover	Bipartite graph
Max-Flow Min-Cut	Max flow value = min cut capacity	Any flow network
Menger's Theorem	Max disjoint paths = min separator size	Any graph, any s-t pair
Cayley's Formula	Labeled trees on n vertices = n to the n-2	Complete graph Kn
Vizing's Theorem	Delta at most edge chromatic number at most Delta + 1	Simple graph
Kirchhoff's Matrix-Tree	Spanning trees = any Laplacian cofactor	Any connected graph

Ready to Test Your Graph Theory Skills?

Practice Euler's theorem, matching algorithms, network flows, and graph coloring problems with our adaptive math tool. Get instant feedback and build confidence for your graph theory and algorithms exams.

Start Practicing Now

Covers all topics from this guide — trees, connectivity, coloring, flows, and algorithms.