Helpful context:

Every meaningful relationship between things - who knows whom, which city connects to which, which atom bonds to which - can be encoded as a graph. The elegance of this observation is not that graphs are complicated but that they are almost absurdly simple: a set of objects (vertices) and a set of pairwise connections (edges). Yet from this minimalist foundation, an entire mathematical discipline has grown that undergirds computer networking, biochemistry, logistics, and the theory of computation itself. When you ask whether two people are connected through a chain of acquaintances, or whether a delivery route can be planned without retracing roads, you are asking graph theory questions.

The discipline has a precise historical birth. In 1736, Leonhard Euler faced a puzzle from the Prussian city of Königsberg: seven bridges connected two islands and two riverbanks; could a walker cross every bridge exactly once and return to the starting point? Euler’s key insight was to strip away everything except what mattered - land masses became vertices, bridges became edges - and to prove that no such walk exists because four vertices had an odd number of incident edges. This argument, the first theorem of graph theory, also introduced the idea that a structural property of the abstract graph (parity of degrees) determines what is and is not achievable, independent of any geometric details.

What follows is a self-contained tour of the core definitions and theorems. The first goal is precision: “connected,” “path,” and “cycle” each carry exact meanings that diverge from casual usage. The second goal is intuition: every definition earns its place by enabling a theorem, and every theorem answers a question you should find natural once the definitions settle.

Basic Definitions

A graph $G = (V, E)$ consists of a finite nonempty set $V$ of vertices and a set $E$ of edges, where each edge is an unordered pair $\{u, v\}$ of distinct vertices. This baseline definition describes a simple undirected graph: no self-loops (an edge from a vertex to itself) and no parallel edges (multiple edges between the same pair). A multigraph relaxes both restrictions. A directed graph (digraph) replaces each unordered pair with an ordered pair $(u, v)$, giving every edge a direction from tail $u$ to head $v$.

The degree $\deg(v)$ of a vertex $v$ in an undirected graph is the number of edges incident to $v$. For digraphs, the in-degree $\deg^-(v)$ counts edges arriving at $v$ and the out-degree $\deg^+(v)$ counts edges leaving $v$. The degree sequence of a graph is the list of vertex degrees sorted in non-increasing order; it is a basic invariant used to distinguish non-isomorphic graphs.

Handshaking Lemma. For any undirected graph $G = (V, E)$,

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

Proof. Each edge $\{u, v\}$ contributes exactly 1 to $\deg(u)$ and exactly 1 to $\deg(v)$, so it contributes exactly 2 to the total sum. Summing over all edges gives $2|E|$. $\square$

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

Proof. Partition $V$ into $V_{\text{odd}}$ (odd-degree vertices) and $V_{\text{even}}$ (even-degree vertices). The sum of degrees over $V_{\text{even}}$ is even. Since the total $2|E|$ is even, the sum over $V_{\text{odd}}$ must also be even, which forces $|V_{\text{odd}}|$ to be even. $\square$

Worked example. A graph on 5 vertices has degree sequence $(4, 3, 3, 2, 2)$. Check: $4+3+3+2+2 = 14 = 2 \times 7$, so $|E| = 7$. There are exactly two odd-degree vertices, consistent with the corollary.

Representations. Two standard data structures encode graphs:

  • Adjacency matrix: an $n \times n$ matrix $A$ where $A_{ij} = 1$ if $\{i,j\} \in E$ and $0$ otherwise. Space: $O(n^2)$. Edge lookup: $O(1)$. Neighbor enumeration: $O(n)$.
  • Adjacency list: an array of $n$ lists, where the $i$-th list contains the neighbors of vertex $i$. Space: $O(n + |E|)$. Edge lookup: $O(\deg(v))$. Neighbor enumeration: $O(\deg(v))$.

For sparse graphs (where $|E| \ll n^2$), adjacency lists are strongly preferred. Adjacency matrices dominate when $O(1)$ edge queries are critical or when matrix-algebraic methods (spectral graph theory) are used.

Discomfort check. The adjacency matrix of a simple undirected graph is always symmetric with zeros on the diagonal. If you see a non-symmetric matrix or nonzero diagonal, the graph is either directed or has self-loops - the definition has shifted beneath you.

Paths, Cycles, Connectivity

These three terms each have a precise meaning, and conflating them is a common source of errors.

A walk of length $k$ from $u$ to $v$ is a sequence $u = v_0, e_1, v_1, e_2, \ldots, e_k, v_k = v$ where each $e_i$ is an edge between $v_{i-1}$ and $v_i$. Vertices and edges may repeat. A trail is a walk in which no edge is repeated. A path is a walk in which no vertex is repeated (which also prevents edge repetition). Every path is a trail; not every trail is a path.

A cycle is a closed trail (start and end at the same vertex, no repeated edges). A simple cycle is a closed path: no repeated vertices except the start/end, and length at least 3.

A graph is connected if there is a path between every pair of vertices. A maximal connected subgraph is a connected component. A graph with $k$ components has no path between vertices in different components.

Worked example. In the graph $1 - 2 - 3 - 1$ (a triangle) with an isolated vertex $4$: the sequence $1, 2, 3, 2$ is a walk but not a trail; $1, 2, 3$ is a path; $1, 2, 3, 1$ is a simple cycle. The graph has two connected components: $\{1,2,3\}$ and $\{4\}$.

For digraphs, connectivity splits into two notions. A digraph is weakly connected if the underlying undirected graph (ignoring edge directions) is connected. It is strongly connected if for every ordered pair $(u, v)$ there is a directed path from $u$ to $v$. A strongly connected component (SCC) is a maximal strongly connected subgraph. Every digraph decomposes into its SCCs, and the “condensation” - the DAG formed by collapsing each SCC to a single node - captures the high-level directed structure.

Discomfort check. Weak connectivity says you can get between any two vertices if you ignore directions. Strong connectivity says you can do it while respecting them. A directed path from $u$ to $v$ does not guarantee a directed path from $v$ to $u$.

Special Graph Families

Complete graph $K_n$. The complete graph on $n$ vertices has every possible edge: $|E| = \binom{n}{2} = \frac{n(n-1)}{2}$. Every vertex has degree $n-1$. $K_n$ is the densest simple graph on $n$ vertices and serves as an extremal benchmark throughout graph theory.

Bipartite graphs. A graph is bipartite if $V$ can be partitioned into two sets $A$ and $B$ such that every edge runs between $A$ and $B$ (no edge is within $A$ or within $B$). The complete bipartite graph $K_{m,n}$ has $|A| = m$, $|B| = n$, and $mn$ edges.

Theorem (Bipartite Characterization). A graph is bipartite if and only if it contains no odd-length cycle.

Proof sketch. If $G$ is bipartite with parts $A$ and $B$, any cycle alternates between $A$ and $B$, so it must have even length. Conversely, if $G$ is connected and contains no odd cycle, pick any vertex $s$ and 2-color $V$ by parity of distance from $s$: color $v$ red if the shortest path from $s$ to $v$ has even length, blue otherwise. If any edge connects two vertices of the same color, the BFS tree path from $s$ to each endpoint, together with that edge, forms an odd cycle - contradiction. The 2-coloring succeeds, so $G$ is bipartite. $\square$

Trees. A tree is a connected acyclic graph. The following three properties each imply the other two for a graph on $n \geq 1$ vertices:

  1. $G$ is connected and acyclic.
  2. $G$ is connected and has exactly $n-1$ edges.
  3. $G$ is acyclic and has exactly $n-1$ edges.

Any tree on $n$ vertices has exactly $n-1$ edges. Adding any edge to a tree creates exactly one cycle; removing any edge disconnects it. Trees are the minimal connected graphs: they have enough edges to be connected but no redundancy.

Planar graphs. A graph is planar if it can be drawn in the plane with no edges crossing. Any such drawing divides the plane into regions called faces, including the unbounded outer face.

Euler’s Formula. For any connected planar graph drawn in the plane,

$$V - E + F = 2,$$

where $V$, $E$, $F$ denote the number of vertices, edges, and faces respectively.

Proof sketch. By induction on $E$. Base case: $E = 0$ means $V = 1$, $F = 1$, and $1 - 0 + 1 = 2$. For $E \geq 1$: if the graph has a cycle, remove one edge of the cycle - this merges two faces into one, so $E$ decreases by 1 and $F$ decreases by 1, keeping $V - E + F$ unchanged. If the graph is a tree ($E = n-1$), then $F = 1$ and $V - E + F = n - (n-1) + 1 = 2$. $\square$

Corollary. For a simple connected planar graph with $V \geq 3$, we have $E \leq 3V - 6$. (Each face is bounded by at least 3 edges, and each edge borders at most 2 faces, giving $3F \leq 2E$; substitute into Euler’s formula.)

This bound immediately shows $K_5$ is non-planar: $V = 5$, $E = 10$, but $3(5) - 6 = 9 < 10$. For $K_{3,3}$: $V = 6$, $E = 9$, and since it is bipartite (no triangles), each face has at least 4 edges, giving $4F \leq 2E$, so $F \leq E/2$; Euler’s formula then gives $6 - 9 + F = 2$, $F = 5$, but $5 \leq 9/2 = 4.5$ - contradiction. By Kuratowski’s theorem, a graph is planar if and only if it contains no subdivision of $K_5$ or $K_{3,3}$ as a subgraph.

Discomfort check. Euler’s formula requires the graph to be connected. For a planar graph with $k$ connected components, the formula becomes $V - E + F = k + 1$.

Graph Isomorphism

Two graphs $G = (V, E)$ and $H = (W, F)$ are isomorphic if there exists a bijection $\phi: V \to W$ such that $\{u, v\} \in E$ if and only if $\{\phi(u), \phi(v)\} \in F$. Isomorphic graphs are structurally identical; they differ only in the labels attached to vertices.

Necessary conditions for isomorphism (none alone is sufficient):

  • Same number of vertices: $|V| = |W|$.
  • Same number of edges: $|E| = |F|$.
  • Identical degree sequences.
  • Same number of cycles of each length.
  • Same chromatic number, same clique number, and so on.

Why necessary conditions are not sufficient. Two non-isomorphic graphs can share all of the above “easy” invariants. The classic example is the pair of non-isomorphic 3-regular graphs on 6 vertices: both have degree sequence $(3,3,3,3,3,3)$ and $9$ edges, but one is $K_{3,3}$ (bipartite) and the other is the prism graph (not bipartite). Bipartiteness distinguishes them, but for larger graphs, distinguishing invariants may be much harder to compute.

Complexity. The graph isomorphism problem (GI) asks: given two graphs, are they isomorphic? It is one of the few natural combinatorial problems not known to be solvable in polynomial time and not known to be NP-complete. In 2015, Babai announced a quasipolynomial-time algorithm ($n^{O(\log n)}$), a major breakthrough, but the polynomial vs. NP-complete question remains open.

Eulerian and Hamiltonian Paths

These two problems sound similar - traverse every edge (or every vertex) exactly once - but their complexities could not be more different.

Euler’s Theorem. A connected undirected graph has an Eulerian circuit (a closed trail traversing every edge exactly once) if and only if every vertex has even degree.

Full proof.

$(\Rightarrow)$ If an Eulerian circuit exists, each time the circuit visits a vertex it uses one entering edge and one leaving edge (or, for the start vertex, one leaving edge initially and one entering edge at the return). Thus each vertex contributes edges in pairs, giving even degree.

$(\Leftarrow)$ Suppose every vertex has even degree. We construct an Eulerian circuit. Start at any vertex $s$ and walk along unused edges, never repeating an edge, until forced to stop. Because every vertex has even degree, whenever the walk enters a vertex, there is always an unused edge to leave by - except possibly at $s$, where we may run out of edges and get stuck. So the walk must close into a circuit $C$ starting and ending at $s$.

If $C$ uses all edges, we are done. Otherwise, since $G$ is connected, some vertex $u$ on $C$ has remaining unused edges. From $u$, repeat the process: walk along unused edges, forming a new circuit $C'$ starting and ending at $u$. Splice $C'$ into $C$ at $u$. Repeat until all edges are used. The result is an Eulerian circuit. $\square$

Eulerian path. A connected graph has an Eulerian path (open trail traversing every edge exactly once) if and only if it has exactly two vertices of odd degree. Those two vertices are the endpoints of the path. This follows from the circuit theorem: add a temporary edge between the two odd-degree vertices (making all degrees even), find an Eulerian circuit, then remove the temporary edge.

Returning to Königsberg. The Königsberg bridge graph has four vertices with degrees $3, 3, 5, 3$ - all odd. No Eulerian path exists (requires exactly 0 or 2 odd-degree vertices). Euler’s proof in 1736 is exactly this argument.

Hamiltonian paths and cycles. A Hamiltonian path visits every vertex exactly once; a Hamiltonian cycle does so and returns to the start. Unlike Eulerian circuits, no simple degree characterization is known. Determining whether a Hamiltonian cycle exists is NP-complete (it encodes the traveling salesman decision problem). Sufficient conditions exist (Dirac’s theorem: if every vertex has degree at least $n/2$, a Hamiltonian cycle exists) but no polynomial-time necessary and sufficient condition is known unconditionally.

Discomfort check. Eulerian means every edge once. Hamiltonian means every vertex once. These are genuinely different problems, and the gap between their computational complexities - polynomial vs. NP-complete - is one of the sharpest contrasts in all of combinatorics.

Graph Coloring

A proper $k$-coloring of $G$ assigns one of $k$ colors to each vertex so that no two adjacent vertices share a color. The chromatic number $\chi(G)$ is the minimum $k$ for which a proper $k$-coloring exists.

Greedy coloring. Order the vertices $v_1, \ldots, v_n$ arbitrarily. Assign to each $v_i$ the smallest color not used by any already-colored neighbor. This always produces a proper coloring, and the color assigned to $v_i$ is at most $1 + |\text{colored neighbors of } v_i|$. Since $|\text{colored neighbors of } v_i| \leq \deg(v_i) \leq \Delta$, where $\Delta = \max_{v} \deg(v)$ is the maximum degree, we get:

$$\chi(G) \leq \Delta + 1.$$

The bound is tight: $K_{\Delta+1}$ achieves $\chi = \Delta + 1$. It can often be improved; for example, Brooks' theorem says $\chi(G) \leq \Delta$ unless $G$ is a complete graph or an odd cycle.

Bipartite iff 2-colorable. A graph is bipartite if and only if $\chi(G) \leq 2$. (A proper 2-coloring is exactly a partition of $V$ into two independent sets, which is the definition of bipartite. No graph with an edge has $\chi = 1$, so for graphs with at least one edge, bipartite is equivalent to $\chi = 2$.)

Four Color Theorem. Every planar graph satisfies $\chi(G) \leq 4$. Stated by Francis Guthrie in 1852, proved by Appel and Haken in 1976 using extensive computer enumeration of roughly 1,500 reducible configurations - the first major theorem whose proof required computer assistance. A shorter computer-aided proof was given by Robertson, Sanders, Seymour, and Thomas in 1997. No purely human-checkable proof is known.

Worked example. For the Petersen graph (10 vertices, 15 edges, 3-regular): $\Delta = 3$, so greedy gives $\chi \leq 4$. The Petersen graph is not bipartite (it has 5-cycles), so $\chi \geq 3$. In fact $\chi = 3$, but proving it requires an explicit 3-coloring - the greedy bound alone does not establish it.

Discomfort check. Chromatic number is a global property: a single vertex forcing a new color raises $\chi$ for the entire graph. Greedy coloring is order-dependent; a bad vertex ordering can use far more than $\chi(G)$ colors. The bound $\chi(G) \leq \Delta + 1$ is worst-case over all orderings.

Summary

Graph type Key property Canonical example Application
Simple graph No loops, no parallel edges Social network General modeling
Complete graph $K_n$ Every pair adjacent $K_5$, $K_{3,3}$ Extremal bounds
Bipartite No odd cycles; 2-colorable $K_{m,n}$ Matching, scheduling
Tree Connected, acyclic, $n-1$ edges Spanning tree Network design, parsing
Planar graph Drawable without crossings; $V-E+F=2$ Triangular grid Circuit layout, mapping
Eulerian graph All degrees even Königsberg fix (add edges) Route inspection
$k$-colorable $\chi(G) \leq k$ Planar $\Rightarrow$ 4-colorable Register allocation, scheduling

Read next: