Graph Theory

A graph is a pair $G=(V,E)$ where $V$ is a finite set of vertices and $E$ is a set of edges, each edge joining two vertices. Graph theory matters because an enormous variety of structures — road networks, molecules, social ties, circuit layouts, scheduling constraints — reduce to vertices-and-edges, so a single theory yields algorithms and theorems usable across disciplines. The field studies invariants (degree, connectivity, chromatic number), structural decompositions (trees, planar embeddings), and optimization (shortest paths, flows, matchings). A surprising fact: whether a graph can be drawn in the plane without edge crossings is characterized by forbidding just two graphs as minors (Kuratowski's Theorem / Wagner's theorem) — an infinite family of constraints collapses to a finite one. Graph theory sits at the boundary of pure combinatorics and applied computer science.

The Core Insight

Almost any system of pairwise relations can be abstracted to a graph, and once abstracted, the same combinatorial tools apply regardless of the original domain. The structure of a graph is governed by local data (vertex degrees, neighborhoods) that constrains global properties (connectivity, cycles, colorability). The art of graph theory is translating a question — "Can we schedule these exams?", "Is this network robust?", "Can this molecule exist?" — into a statement about vertices and edges, then exploiting universal theorems.

Formal Statement

Graph

A (simple, undirected) graph is an ordered pair $G=(V,E)$ where:

• $V$ is a finite nonempty set of vertices (also nodes),
• $E\subseteq \left(\genfrac{}{}{0ex}{}{V}{2}\right)$ is a set of edges, each an unordered pair $\{u,v\}$ of distinct vertices.

We write $n=|V|$ for the order and $m=|E|$ for the size. Two vertices joined by an edge are adjacent; an edge is incident to its endpoints. Variants:

• A multigraph allows multiple edges between the same pair.
• A graph with loops allows edges $\{v,v\}$.
• A directed graph (digraph) uses ordered pairs $E\subseteq V\times V$ (arcs).
• A weighted graph assigns $w:E\to \mathbb{R}$.

Degree

The degree $\mathrm{deg}(v)$ of a vertex $v$ is the number of edges incident to it. In a simple graph,

The minimum and maximum degrees are $\delta (G)={\min }_v\mathrm{deg}(v)$ and $\Delta (G)={\max }_v\mathrm{deg}(v)$.

Handshaking Lemma

For any finite graph $G=(V,E)$,

A corollary: the number of vertices of odd degree is even.

Adjacency Matrix

For $V=\{v_1,\dots ,v_n\}$, the adjacency matrix $A=(a_{ij})$ is the $n\times n$ matrix with

The number of walks of length $k$ from $v_i$ to $v_j$ equals the $(i,j)$ entry of $A^k$:

Connectivity and Paths

A walk is an alternating sequence of vertices and edges; a path is a walk with no repeated vertex; a cycle is a closed path. $G$ is connected if every pair of vertices is joined by a path. A maximal connected subgraph is a connected component. The distance $d(u,v)$ is the length of a shortest $u$–$v$ path (or $\infty$).

Why It Holds / Derivation

Handshaking Lemma

We prove equation [2].

1. Consider the set of incidences $I=\{(v,e):v\in V,e\in E,v\text{ is an endpoint of }e\}$.
2. Count $|I|$ by vertices. For each vertex $v$, the number of incidences involving $v$ is exactly $\mathrm{deg}(v)$ (one per incident edge). Hence $|I|={\sum }_{v\in V}\mathrm{deg}(v)$.
3. Count $|I|$ by edges. Each edge $e=\{u,w\}$ has exactly two endpoints, contributing exactly $2$ incidences. Hence $|I|=2|E|=2m$.
4. Equating the two counts: ${\sum }_v\mathrm{deg}(v)=2m$. $■$

Walk-Counting Formula

We prove [5] by induction on $k$.

1. Base $k=1$: $(A^1{)}_{ij}=a_{ij}$ counts the walks of length 1 (single edges) from $i$ to $j$. True.
2. Inductive step: Assume $(A^{k-1}{)}_{i\ell }$ counts walks of length $k-1$ from $i$ to $\ell$. A walk of length $k$ from $i$ to $j$ is a walk of length $k-1$ from $i$ to some intermediate vertex $\ell$, followed by an edge $\{\ell ,j\}$.
3. Summing over all valid $\ell$:

1. The right side counts exactly all length-$k$ walks, completing the induction. $■$

Leonhard Euler | 1707–1783

Euler launched graph theory in 1736 by solving the Seven Bridges of Königsberg: could a citizen cross each of the city's seven bridges exactly once and return home? Euler abstracted the four landmasses into vertices and the bridges into edges, then showed the walk is impossible because more than two vertices had odd degree. This established the principle — still central — that the answer depends only on the abstract incidence structure, not on geometry. Euler also gave the polyhedral formula $V-E+F=2$, foundational to planar graph theory and topology. His genius was recognizing that a physical puzzle reduces to a counting argument over degrees.

Building Intuition

Think of a graph as a "relationship diagram." Vertices are entities; an edge means "these two are directly linked." Almost every property has a tangible reading:

• Degree = popularity / number of direct connections.
• Connected = you can travel between any two points.
• Path = a route with no backtracking through the same place.
• Cycle = a round trip returning to start.
• Bipartite = the entities split into two camps, with links only between camps (think jobs vs. applicants).
• Tree = a minimally connected network — remove any edge and it falls apart; add any edge and you create a loop.

The handshaking lemma is just "at a party, the total number of handshake-ends is twice the number of handshakes." The adjacency-matrix power trick says "to count $k$-step journeys, multiply the one-step map by itself $k$ times" — propagation of reachability through repeated composition.

A simple graph with five vertices, showing degrees and a highlighted cycle

Worked Examples

Verifying the Handshaking Lemma

• $a$: edges $\{a,b\},\{a,d\}$ → $\mathrm{deg}(a)=2$
• $b$: edges $\{a,b\},\{b,c\},\{d,b\}$ → $\mathrm{deg}(b)=3$
• $c$: edges $\{b,c\},\{c,e\}$ → $\mathrm{deg}(c)=2$
• $d$: edges $\{a,d\},\{d,b\},\{e,d\}$ → $\mathrm{deg}(d)=3$
• $e$: edges $\{c,e\},\{e,d\}$ → $\mathrm{deg}(e)=2$

Counting walks via matrix powers

Common Misconceptions

• Walk: vertices/edges may repeat.
• Trail: no repeated edge (vertices may repeat).
• Path: no repeated vertex (hence no repeated edge).
• Cycle/Circuit: closed; a cycle additionally has no repeated internal vertex.

Confusing these breaks theorems: an Eulerian trail uses every edge once; a Hamiltonian path uses every vertex once. These are vastly different in difficulty — Eulerian existence is decided instantly by degree parity, while Hamiltonicity is NP-complete.

Degree sequence does not determine the graph

Two graphs can have identical degree sequences yet not be isomorphic. Consider degree sequence $(2,2,2,2,2,2)$ on six vertices:

• Graph A: a single 6-cycle $C_6$.
• Graph B: two disjoint triangles $C_3+C_3$.

Both have every vertex of degree 2 and satisfy [2] ($\sum \mathrm{deg}=12=2m$, $m=6$). But $C_6$ is connected while $2C_3$ is not — they are not isomorphic. Hence the degree sequence is a necessary but not sufficient invariant for graph identity.

Connections

Graph theory connects to many areas:

• Linear Algebra: the adjacency and Laplacian Matrix turn graph questions into eigenvalue problems (spectral graph theory); eigenvalues bound connectivity, expansion, and colorability.
• Topology: planar graphs and the Euler characteristic $V-E+F=2$ link to surfaces and embeddings; graph minors relate to topological structure.
• Combinatorics: enumeration (counting trees via Cayley's Formula), extremal results (Turán-type theorems), and Ramsey theory all live here.
• Probability Theory: random graphs $G(n,p)$ exhibit sharp threshold phenomena and underlie network science.
• Computational Complexity: many canonical NP-complete problems (Hamiltonian cycle, graph coloring, clique) are graph problems; others (shortest path, max flow) are polynomial.
• Group Theory: the automorphism group of a graph and Cayley graphs bridge algebra and combinatorics.

Real-World Applications

1. Internet routing (OSPF, BGP): networks modeled as weighted graphs; Dijkstra's and Bellman–Ford algorithms compute shortest paths for packet delivery.
2. Google's PageRank: the web is a directed graph; importance is the dominant eigenvector of a stochastic adjacency-derived matrix — spectral graph theory in production.
3. Compiler register allocation: variables are vertices, "alive simultaneously" is an edge; assigning CPU registers without conflict is graph coloring of the interference graph.
4. Chemistry (molecular graphs): atoms are vertices, bonds are edges; isomer enumeration, the Wiener index, and QSAR property prediction use graph invariants.
5. Project scheduling (PERT/CPM): tasks form a directed acyclic graph; the critical path (longest path) determines minimum project duration.
6. Social network analysis: centrality, community detection, and influence spread are graph algorithms on friendship/follower graphs.
7. VLSI circuit layout & airline scheduling: planarity testing minimizes wire crossings; bipartite matching assigns crews to flights optimally.

Historical Development

• 1736 — Euler solves the Seven Bridges of Königsberg, founding graph theory and characterizing Eulerian walks via degree parity.
• 1750 — Euler states the polyhedral formula $V-E+F=2$, later central to planar graphs.
• 1847 — Gustav Kirchhoff applies tree-counting to electrical networks (Kirchhoff's matrix-tree theorem).
• 1852 — Francis Guthrie poses the Four Color Problem (can every planar map be colored with four colors?).
• 1857 — Arthur Cayley studies trees while enumerating chemical isomers; later proves $n^{n-2}$ labeled trees.
• 1936 — Dénes Kőnig publishes the first textbook on graph theory, consolidating the field.
• 1930 — Kazimierz Kuratowski characterizes planar graphs by forbidden subgraphs $K_5$ and $K_{3,3}$.
• 1956 — Edsger Dijkstra (pub. 1959) and contemporaries develop shortest-path and max-flow (Ford–Fulkerson, 1956) algorithms, launching algorithmic graph theory.
• 1976 — Appel and Haken prove the Four Color Theorem with computer assistance — the first major theorem requiring a computer.
• 1983–2004 — Robertson and Seymour's Graph Minors project proves every minor-closed family is characterized by finitely many forbidden minors.

Subtleties & Limits

Several deep questions remain partly open or computationally hard:

• Graph Isomorphism: is there a polynomial-time algorithm to decide whether two graphs are isomorphic? Babai (2015) gave a quasi-polynomial algorithm, but its exact complexity status (P vs NP-intermediate) is unresolved.
• Hamiltonicity & the Traveling Salesman: deciding whether a Hamiltonian cycle exists is NP-complete; no efficient characterization analogous to Eulerian degree-parity is known.
• Reconstruction Conjecture (Kelly–Ulam, 1942): is every graph on $\ge 3$ vertices uniquely determined (up to isomorphism) by its multiset of vertex-deleted subgraphs? Still open.
• Chromatic number bounds: while $\chi (G)\le \Delta (G)+1$ always holds (and Brooks's theorem refines it), computing $\chi$ exactly is NP-hard, and structural conjectures (e.g., Hadwiger's conjecture relating $\chi$ to minors) remain unproven in general.

See Also