Graph Theory: A Mathematical Overview

2022-09-14

graph theorymathematicsdiscrete mathematicscombinatorics

An exploration of graph theory’s mathematical foundations—from Euler’s bridges to modern network analysis.

I. Origins: The Bridges of Königsberg

In 1736, Leonhard Euler considered a puzzle that had amused the citizens of Königsberg: could one walk through the city, crossing each of its seven bridges exactly once, and return to the starting point?

The city straddled the Pregel River, with two islands connected to each other and to the riverbanks by seven bridges. The citizens had tried and failed to find such a path. Euler proved it impossible—and in doing so, invented graph theory.

Euler’s insight was to strip away the geography. The landmasses became points; the bridges became lines connecting them. The physical city transformed into an abstract structure: four vertices, seven edges. The question became purely topological: does there exist a closed walk that traverses each edge exactly once?

Euler proved that such a walk—now called an Eulerian circuit—exists if and only if every vertex has even degree. Königsberg’s graph had four vertices of odd degree. The walk was impossible, and mathematics had gained a new branch.

II. Fundamental Definitions

A graph $G$ is an ordered pair $(V, E)$ where $V$ is a finite set of vertices and $E$ is a set of edges, each edge being a pair of vertices.

In an undirected graph, edges are unordered pairs: $\{u, v\} = \{v, u\}$. In a directed graph (digraph), edges are ordered pairs: $(u, v) \neq (v, u)$.

The degree of a vertex $v$, denoted $\deg(v)$, is the number of edges incident to it. In directed graphs, we distinguish in-degree (edges pointing to $v$) from out-degree (edges pointing from $v$).

A graph is simple if it contains no loops (edges from a vertex to itself) and no multiple edges between the same pair of vertices. Unless otherwise specified, “graph” typically means “simple undirected graph.”

A weighted graph assigns a numerical value to each edge, representing cost, distance, capacity, or any other quantity of interest.

III. The Handshaking Lemma

The first theorem of graph theory emerges from a simple observation:

$$\sum_{v \in V} \deg(v) = 2|E|$$

Every edge contributes exactly 2 to the sum of degrees—one for each endpoint. This is the Handshaking Lemma, so named because if vertices represent people and edges represent handshakes, then the total number of hands shaken must be even.

A corollary: every graph has an even number of vertices with odd degree. This seemingly trivial result proved the impossibility of the Königsberg walk and continues to constrain graph constructions today.

IV. Paths, Walks, and Cycles

A walk is a sequence of vertices $v_0, v_1, \ldots, v_k$ where each consecutive pair is connected by an edge. The length of a walk is the number of edges traversed.

A path is a walk with no repeated vertices. A trail is a walk with no repeated edges. The distinction matters: one can revisit vertices while avoiding edge repetition (trail), or avoid revisiting vertices entirely (path).

A cycle is a path that returns to its starting vertex: $v_0, v_1, \ldots, v_k, v_0$ with $k \geq 2$ and all intermediate vertices distinct.

The distance between vertices $u$ and $v$, denoted $d(u, v)$, is the length of the shortest path between them—or $\infty$ if no path exists.

V. Connectivity

A graph is connected if a path exists between every pair of vertices. Otherwise, it decomposes into connected components—maximal connected subgraphs.

For directed graphs, we distinguish:

Weakly connected: connected if we ignore edge directions
Strongly connected: a directed path exists from every vertex to every other vertex

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 concepts identify structural vulnerabilities—the single points of failure in a network.

The vertex connectivity $\kappa(G)$ is the minimum number of vertices whose removal disconnects $G$. The edge connectivity $\lambda(G)$ is the minimum number of edges whose removal disconnects $G$. Menger’s theorem relates these to the maximum number of independent paths between vertices.

VI. Special Graphs

Certain graph families recur throughout theory and application:

Complete Graph $K_n$: Every pair of $n$ vertices is connected. Contains $\binom{n}{2} = \frac{n(n-1)}{2}$ edges.

Bipartite Graph: Vertices partition into two sets $A$ and $B$ such that every edge connects a vertex in $A$ to a vertex in $B$. No edges exist within $A$ or within $B$.

Complete Bipartite Graph $K_{m,n}$: Every vertex in $A$ (of size $m$) connects to every vertex in $B$ (of size $n$). Contains $mn$ edges.

Cycle Graph $C_n$: A single cycle of $n$ vertices. Each vertex has degree 2.

Tree: A connected graph with no cycles. Equivalently, a connected graph with exactly $n - 1$ edges for $n$ vertices. Between any two vertices, exactly one path exists.

Planar Graph: Can be drawn in the plane with no edge crossings. Euler’s formula constrains planar graphs: $v - e + f = 2$, where $f$ is the number of faces (regions bounded by edges, including the infinite outer region).

VII. Graph Coloring

A proper vertex coloring assigns colors to vertices such that no two adjacent vertices share a color. The chromatic number $\chi(G)$ is the minimum number of colors required.

For the complete graph, $\chi(K_n) = n$—every vertex needs its own color. For bipartite graphs, $\chi(G) = 2$. For cycle graphs, $\chi(C_n) = 2$ if $n$ is even, $3$ if odd.

The Four Color Theorem states that every planar graph satisfies $\chi(G) \leq 4$. Conjectured in 1852, it resisted proof until 1976, when Appel and Haken verified it through extensive computer enumeration of cases—the first major theorem proved with computational assistance.

Edge coloring assigns colors to edges such that no two edges sharing a vertex have the same color. Vizing’s theorem bounds the chromatic index: for any simple graph, either $\Delta$ or $\Delta + 1$ colors suffice, where $\Delta$ is the maximum degree.

VIII. Trees and Spanning Trees

Trees occupy a privileged position in graph theory. They are minimally connected: removing any edge disconnects them. They are maximally acyclic: adding any edge creates a cycle.

Equivalent characterizations of trees (for a graph $G$ with $n$ vertices):

$G$ is connected and has $n - 1$ edges
$G$ is connected and has no cycles
$G$ has no cycles and has $n - 1$ edges
Between any two vertices, exactly one path exists

A spanning tree of a connected graph $G$ is a subgraph that includes all vertices and is itself a tree. Every connected graph has at least one spanning tree.

For weighted graphs, a minimum spanning tree (MST) is a spanning tree with minimum total edge weight. Kruskal’s and Prim’s algorithms find MSTs efficiently. Applications range from network design (minimizing cable length) to clustering (grouping similar data points).

IX. Eulerian and Hamiltonian Graphs

Returning to Euler’s original question: an Eulerian path traverses every edge exactly once. An Eulerian circuit is an Eulerian path that returns to its start.

Euler’s Theorem: A connected graph has an Eulerian circuit if and only if every vertex has even degree. It has an Eulerian path if and only if exactly zero or two vertices have odd degree.

A Hamiltonian path visits every vertex exactly once. A Hamiltonian cycle is a Hamiltonian path that returns to its start.

Unlike the Eulerian case, no simple characterization exists for Hamiltonian graphs. Determining whether a graph is Hamiltonian is NP-complete—one of the fundamental hard problems in computer science. This asymmetry between edges and vertices pervades graph theory: edge problems often yield to elegant solutions while vertex problems resist.

X. Planar Graphs and Euler’s Formula

A graph is planar if it can be embedded in the plane without edge crossings. Such an embedding divides the plane into faces—regions bounded by edges.

Euler’s Formula for connected planar graphs:

$$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 constrains planar graphs. Since each face is bounded by at least 3 edges, and each edge borders at most 2 faces:

$$e \leq 3v - 6$$

The complete graph $K_5$ has 10 edges but only 5 vertices: $10 > 3(5) - 6 = 9$. Therefore $K_5$ is not planar. Similarly, $K_{3,3}$ violates a related bound and is not planar.

Kuratowski’s Theorem: A graph is planar if and only if it contains no subdivision of $K_5$ or $K_{3,3}$. These two graphs are the fundamental obstructions to planarity.

XI. Spectral Graph Theory

The adjacency matrix $A$ of a graph $G$ with $n$ vertices is an $n \times n$ matrix where $A_{ij} = 1$ if vertices $i$ and $j$ are adjacent, and $0$ otherwise.

The eigenvalues of $A$ encode structural information about $G$. The largest eigenvalue relates to the maximum degree. The number of zero eigenvalues relates to connected components. The eigenvalue distribution influences random walks, graph expansion, and network resilience.

The Laplacian matrix $L = D - A$, where $D$ is the diagonal matrix of degrees, has non-negative eigenvalues. The number of zero eigenvalues equals the number of connected components. The second-smallest eigenvalue—the algebraic connectivity or Fiedler value—measures how well-connected the graph is.

Spectral methods power graph partitioning algorithms, community detection in networks, and dimensionality reduction techniques. The marriage of linear algebra and combinatorics yields insights neither discipline achieves alone.

XII. Random Graphs

The Erdős–Rényi model $G(n, p)$ generates random graphs: start with $n$ vertices and include each possible edge independently with probability $p$.

As $p$ increases, random graphs undergo phase transitions. Below a critical threshold, the graph consists of small, isolated components. Above the threshold, a giant component emerges containing a constant fraction of all vertices. The transition is sharp—a qualitative change in structure from an infinitesimal change in parameters.

Random graph theory illuminates the typical behavior of graphs, complementing the worst-case analysis of algorithmic complexity. It models real-world networks, from social connections to the web, where edges form through probabilistic processes rather than deliberate design.

XIII. Modern Directions

Contemporary graph theory extends in numerous directions:

Network Science applies graph theory to complex systems—social networks, biological networks, infrastructure networks. Concepts like degree distributions, clustering coefficients, and centrality measures characterize real-world network structure.

Algebraic Graph Theory studies graphs through their algebraic invariants—automorphism groups, characteristic polynomials, graph homomorphisms.

Extremal Graph Theory asks: what is the maximum or minimum number of edges a graph can have while satisfying certain properties? The Turán problem, Ramsey theory, and regularity lemmas belong to this domain.

Graph Algorithms develops efficient methods for graph problems—shortest paths, network flows, matching, coloring. The interplay between theoretical complexity and practical computation drives both fields forward.

XIV. The Abstract and the Concrete

Graph theory began with a recreational puzzle about bridges. It now permeates mathematics, computer science, physics, biology, and social science. The abstraction that Euler discovered—reducing physical structure to vertices and edges—has proven endlessly fertile.

Perhaps this is because relationships are fundamental. Before we count, we connect. Before we measure, we relate. The graph is the mathematical structure that captures pure relation, stripped of all other attributes. In studying graphs, we study the skeleton of structure itself.

From Königsberg’s bridges to the architecture of the internet, from molecular bonds to social ties, graph theory provides the language for describing how things connect. The mathematics is old now, nearly three centuries, yet every year brings new applications, new theorems, new depths.

Euler would recognize the field he founded. He would also, one suspects, be astonished by how far his bridges have carried us.

Graph Theory: A Mathematical Overview