Graph Theory

⚡ Key Takeaways

Graph theory studies graphs — collections of objects (vertices) connected pairwise by relations (edges). One-line statement: a graph $G=(V,E)$ encodes which pairs of a set are related. Key result in words: deep structure (connectivity, colorability, planarity, matchings, flows) follows from simple combinatorial axioms. Applies in computer science, networks, chemistry, operations research, and discrete optimization. Founded by Leonhard Euler in 1736 with the Königsberg bridges problem; matured in the 19th–20th centuries.

💡 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.

DefinitionGraph

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

$V$ is a finite nonempty set of vertices (also nodes),
$E \subseteq \binom{V}{2}$ 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}$ .

DefinitionDegree

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

1

\quad \deg(v) = |\{u \in V : \{u,v\}\in E\}|.

Derivation hint: count neighbors directly; each adjacency contributes exactly one to the count. The minimum and maximum degrees are $\delta(G)=\min_v \deg(v)$ and $\Delta(G)=\max_v \deg(v)$ .

TheoremHandshaking Lemma

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

2

\quad \sum_{v\in V} \deg(v) = 2m.

Derivation hint: each edge has two endpoints, so summing degrees double-counts every edge. A corollary: the number of vertices of odd degree is even.

3

\quad \big|\{v : \deg(v)\text{ odd}\}\big| \equiv 0 \pmod 2.

Derivation hint: split the sum in [2] into odd- and even-degree parts; the total is even, the even part is even, so the odd part has even cardinality.

DefinitionAdjacency Matrix

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

4

\quad a_{ij} = \begin{cases} 1 & \{v_i,v_j\}\in E,\\ 0 & \text{otherwise.}\end{cases}

Derivation hint: read off adjacency as a 0/1 incidence indicator; for simple graphs $A$ is symmetric with zero diagonal. The number of walks of length $k$ from $v_i$ to $v_j$ equals the $(i,j)$ entry of $A^k$ :

5

\quad (\text{walks of length }k\text{ from }i\text{ to }j) = (A^k)_{ij}.

Derivation hint: induct on $k$ ; matrix multiplication sums over all intermediate vertices, exactly enumerating concatenations of a walk of length $k-1$ with one edge.

DefinitionConnectivity 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$ ).

ProofHandshaking 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 $\deg(v)$ (one per incident edge). Hence $|I| = \sum_{v\in V}\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 \deg(v) = 2m$ . $\blacksquare$

∎

ProofWalk-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$ :

6

\quad (A^k)_{ij} = \sum_{\ell=1}^{n} (A^{k-1})_{i\ell}\, a_{\ell j}.

Derivation hint: this is the definition of matrix multiplication $A^k = A^{k-1}A$ ; each term counts (walks to $\ell$ ) × (edge $\ell\to j$ ). 4. The right side counts exactly all length- $k$ walks, completing the induction. $\blacksquare$

∎

mathematician · 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.

🧠 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.

Figure

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

ExampleVerifying the Handshaking Lemma

Given: A graph on $V=\{a,b,c,d,e\}$ with edges $\{a,b\},\{b,c\},\{a,d\},\{d,b\},\{c,e\},\{e,d\}$ . So $m=6$ .

Step 1 — compute degrees.

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

Step 2 — sum degrees. $2+3+2+3+2 = 12$ .

Step 3 — check against $2m$ . $2m = 2\cdot 6 = 12$ . ✓

Step 4 — odd-degree count. Odd-degree vertices: $b,d$ → exactly $2$ , which is even, consistent with [3].

\boxed{\sum_v \deg(v) = 12 = 2m,\quad \#\text{odd-degree} = 2 \text{ (even)}}

ExampleCounting walks via matrix powers

Given: A path graph $P_3$ on vertices $1\!-\!2\!-\!3$ with adjacency matrix

7

\quad A = \begin{pmatrix} 0&1&0\\ 1&0&1\\ 0&1&0 \end{pmatrix}.

Derivation hint: entry 1 marks each adjacent pair; vertex 2 is the center adjacent to both ends.

Step 1 — square $A$ .

8

\quad A^2 = \begin{pmatrix} 1&0&1\\ 0&2&0\\ 1&0&1 \end{pmatrix}.

Derivation hint: multiply $A\cdot A$ ; $(A^2)_{22}=2$ since vertex 2 reaches itself via $2\to1\to2$ and $2\to3\to2$ .

Step 2 — interpret entries. Number of length-2 walks from vertex 1 to vertex 3 is $(A^2)_{13}=1$ (the walk $1\to2\to3$ ). Number of length-2 closed walks at center vertex 2 is $(A^2)_{22}=2$ .

Step 3 — total closed length-2 walks $= \mathrm{tr}(A^2) = 1+2+1 = 4 = 2m$ (each edge traversed forward+back gives 2 closed walks; $m=2$ edges → 4). ✓

\boxed{\text{length-2 walks }1\to3 = 1,\quad \mathrm{tr}(A^2)=4=2m}

⚠️ Common mistake

"A walk, path, trail, and cycle are the same thing." They are not:

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.

CounterexampleDegree 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\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.

connection

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.
<a class="wiki-link" href="/wiki/probability-theory">Probability Theory</a>: 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.

🔬 Where this appears

⏳ History

- 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.

open-problem

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.

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also