Graph Theory

Last updated: August 2026

Disclaimer: These are my personal notes compiled for my own reference and learning. They may contain errors, incomplete information, or personal interpretations. While I strive for accuracy, these notes are not peer-reviewed and should not be considered authoritative sources. Please consult official textbooks, research papers, or other reliable sources for academic or professional purposes.

Contents

  1. Basic definitions and the Handshake Lemma
  2. Trees: equivalent characterizations
  3. Euler's formula for planar graphs
  4. Edge bounds and non-planarity of $K_5$, $K_{3,3}$
  5. The Five Color Theorem
  6. Matchings and König's theorem
  7. Hall's Marriage Theorem
  8. Eulerian circuits
  9. Computation
  10. Common pitfalls
  11. Connections
  12. References

1. Basic definitions and the Handshake Lemma

Definitions

A (simple) graph $G=(V,E)$: a vertex set $V$ and a set $E$ of unordered pairs of distinct vertices. $\deg(v)$: the number of edges incident to $v$. $G$ is bipartite if $V$ splits into $A\sqcup B$ with every edge crossing between $A$ and $B$. A path visits distinct vertices in sequence via edges; a cycle is a path returning to its start.

Theorem (Handshake Lemma)

$\sum_{v\in V}\deg(v)=2|E|$; consequently the number of odd-degree vertices is even.

Proof. Each edge $\{u,v\}$ contributes exactly $1$ to $\deg(u)$ and $1$ to $\deg(v)$ — exactly $2$ to the sum, regardless of which edge. Summing over all $|E|$ edges gives $2|E|$. Since $2|E|$ is even, the sum of degrees is even; a sum of integers is even iff the number of odd terms among them is even, so the odd-degree vertices number even. ∎

2. Trees: equivalent characterizations

Definition

A tree is a connected, acyclic graph.

Lemma (Leaf lemma)

Every tree with at least $2$ vertices has a vertex of degree $1$ (a leaf).

Proof. Take a longest path $v_0,\ldots,v_k$ in the (finite) tree; $k\geq1$ since the tree has $\geq2$ vertices and is connected. If $v_k$ had a neighbor $u\neq v_{k-1}$: $u$ cannot be $v_i$ for any $i<k-1$, since the tree's acyclicity means there is a unique path between any two vertices, and $u=v_i$ would give two distinct paths from $v_i$ to $v_k$ (along the original path, and via the direct edge $v_k u$) — a cycle. So $u$ is not on the path at all, and $v_0,\ldots,v_k,u$ is a longer path, contradicting maximality. So $v_k$'s only neighbor is $v_{k-1}$: degree $1$. ∎
Theorem

A graph on $n$ vertices is a tree iff it is connected with exactly $n-1$ edges, iff it is acyclic with exactly $n-1$ edges.

Proof. Tree $\Rightarrow$ $n-1$ edges: induction on $n$. $n=1$: $0$ edges. $n\geq2$: by the Leaf Lemma, some leaf $v$ exists; $G-v$ (remove $v$ and its one edge) is still a tree, now on $n-1$ vertices, with $n-2$ edges by the induction hypothesis; adding $v$'s single edge back gives $n-1$. Acyclic with $n-1$ edges $\Rightarrow$ connected (hence a tree): if it had $k\geq2$ components, each component is itself a tree (connected, acyclic) on its own vertex set, so by the direction just proved, component $i$ (with $n_i$ vertices) has $n_i-1$ edges; summing, total edges $=\sum(n_i-1)=n-k\leq n-2$, contradicting $n-1$ edges. So $k=1$. Connected with $n-1$ edges $\Rightarrow$ acyclic (hence a tree): if a cycle existed, removing one of its edges keeps the graph connected (a cycle edge is never a bridge) with $n-2$ edges and $n$ vertices — but every connected graph needs at least $n-1$ edges (a spanning tree's worth, extractable by repeatedly dropping cycle edges), so $n-2\geq n-1$ is a contradiction. ∎

3. Euler's formula for planar graphs

Theorem (Euler's formula)

For a connected planar graph drawn in the plane with $n$ vertices, $m$ edges, and $f$ faces (including the unbounded outer face): $n-m+f=2$.

Proof. By induction on $m$. If $G$ is a tree ($m=n-1$, Section 2), it bounds no enclosed region when drawn in the plane, so $f=1$ (just the outer face): $n-(n-1)+1=2$. Otherwise $G$ has a cycle; removing one edge $e$ on that cycle keeps $G-e$ connected (a cycle edge is never a bridge) and merges the two faces $e$ bordered into one, so $f$ decreases by exactly $1$. Applying the induction hypothesis to $G-e$ (with $n$ vertices, $m-1$ edges, $f-1$ faces): $n-(m-1)+(f-1)=2$, i.e. $n-m+f=2$. ∎

Figure 1 verifies this directly by construction: repeatedly stacking a new vertex inside a face (connecting it to that face's three boundary vertices) adds exactly $1$ vertex, $3$ edges, and (splitting one face into three) $2$ faces at each step — so $n-m+f$ changes by $1-3+2=0$, staying at $2$ forever, exactly the induction step of the proof above, run forward rather than backward.

Left panel: a triangulated planar graph built by repeatedly subdividing the largest remaining triangular face. Right panel: the vertex count, edge count, and face count all growing linearly with construction step, while their alternating sum n minus m plus f stays flat at exactly 2 throughout.
Figure — Euler's formula, verified through an actual triangulation construction. Left: a planar triangulation built by repeatedly splitting the current largest face into three with a new central vertex. Right: across $24$ such steps, $n$, $m$, and $f$ all grow, but $n-m+f$ never moves from $2$ — the invariant Section 3 proves is preserved by exactly this construction, checked numerically at every single step.

4. Edge bounds and non-planarity of $K_5$, $K_{3,3}$

Corollary

A simple connected planar graph with $n\geq3$ vertices has $m\leq3n-6$ edges; if additionally triangle-free, $m\leq2n-4$.

Proof. Each face is bounded by at least $3$ edges (simple graph: no loops or repeated edges bounding a face with fewer), and each edge borders at most $2$ faces, so $3f\leq2m$. Substituting $f=2-n+m$ (Euler's formula): $3(2-n+m)\leq2m\Rightarrow6-3n+3m\leq2m\Rightarrow m\leq3n-6$. If triangle-free, every face is bounded by $\geq4$ edges instead, giving $4f\leq2m$ and, by the same substitution, $m\leq2n-4$. ∎
Corollary

$K_5$ and $K_{3,3}$ are not planar.

Proof. $K_5$: $n=5$, $m=10$; but $3n-6=9<10$. $K_{3,3}$: bipartite, hence triangle-free; $n=6$, $m=9$; but $2n-4=8<9$. Both violate the edge bound above, so neither can be drawn planar. ∎

(Kuratowski's theorem — a graph is planar iff it contains no subdivision of $K_5$ or $K_{3,3}$ — is the converse, that these two obstructions are the only ones; it is a substantially harder theorem and not proved here.)

5. The Five Color Theorem

Theorem (Five Color Theorem)

Every simple planar graph is $5$-colorable.

Proof (sketch, Kempe chains). Induction on $n$. If $\Delta(G)\leq4$ everywhere the greedy bound $\chi\leq\Delta+1$ finishes immediately; more generally, Section 4's edge bound forces some vertex $v$ with $\deg(v)\leq5$ (else $\sum\deg\geq6n$, i.e. $m\geq3n>3n-6$, contradiction). Remove $v$; by the induction hypothesis $5$-color $G-v$. If $v$'s neighbors use at most $4$ colors, a free color remains for $v$. Otherwise $v$ has exactly $5$ neighbors using all $5$ colors, in some cyclic order around $v$ in the planar embedding; label them $u_1,\ldots,u_5$ with colors $1,\ldots,5$. Consider the subgraph induced by colors $1$ and $3$: if $u_1$ and $u_3$ lie in different connected components of it, swap colors $1\leftrightarrow3$ throughout $u_1$'s component — this does not affect any vertex outside that component (in particular not $u_3$, still colored $3$), and frees color $1$ for $v$. If instead $u_1,u_3$ are connected by an alternating $1$-$3$ path (a "Kempe chain"), that chain together with $v$ encloses a region of the plane containing $u_2$ but not $u_4$ (a planarity fact, from the cyclic order $u_1,u_2,u_3,u_4,u_5$ around $v$), so the $2$-$4$ subgraph cannot connect $u_2$ to $u_4$ — swap colors $2\leftrightarrow4$ in $u_2$'s component instead, freeing color $2$ for $v$. ∎

This proof is completely elementary and predates computers by nearly a century (Heawood, 1890, correcting an earlier flawed proof of Kempe's own four-color attempt). The stronger Four Color Theorem (every planar graph is $4$-colorable, without the "or" case escape this proof relies on at color $5$) resisted every hand proof attempt for a century and was finally settled by Appel and Haken (1976) via an exhaustive, computer-verified case analysis of $1{,}936$ unavoidable configurations — the first major theorem in mathematics whose proof no human has ever fully checked by hand, and Section 10's first pitfall returns to why that mattered.

6. Matchings and König's theorem

Definitions

A matching is a set of edges with no shared endpoints. A vertex cover is a set of vertices touching every edge. An augmenting path for matching $M$ is a path alternating between edges outside and inside $M$, starting and ending at $M$-unmatched vertices.

Lemma (any graph)

max matching size $\leq$ min vertex cover size.

Proof. A vertex cover must contain at least one endpoint of every matching edge; since matching edges share no endpoints, these required cover vertices are all distinct — one per matching edge, at minimum. ∎
Lemma (Berge)

$M$ is a maximum matching iff no $M$-augmenting path exists.

Proof. If an augmenting path $P$ exists, flipping membership in $M$ along $P$ (edges in $M$ leave, edges not in $M$ join) strictly increases the matching size by $1$, so $M$ was not maximum. Conversely, if $M$ is not maximum, let $M'$ be larger; $M\triangle M'$ (symmetric difference) has maximum degree $2$ (each vertex touches at most one edge from each matching), so it decomposes into disjoint paths and cycles alternating between $M$- and $M'$-edges. Since $|M'|>|M|$, some component has more $M'$-edges than $M$-edges, which (alternation) forces it to be a path beginning and ending with $M'$-edges — exactly an $M$-augmenting path. ∎
Theorem (König)

In a bipartite graph, max matching size $=$ min vertex cover size.

Proof (sketch). Let $M$ be a maximum matching in $G=(A\cup B,E)$, $U\subseteq A$ its unmatched vertices in $A$, and $Z$ the set of vertices reachable from $U$ by $M$-alternating paths. Let $C=(A\setminus Z)\cup(B\cap Z)$. $C$ covers every edge: an edge with its $A$-endpoint outside $Z$ is covered there; an edge with its $A$-endpoint in $Z$ either extends an alternating path into its $B$-endpoint (putting that endpoint in $Z\cap B\subseteq C$) or, if it is itself a matching edge, its $B$-endpoint is likewise reachable and in $C$. Every vertex of $C$ is $M$-matched (unmatched $A$-vertices are all in $U\subseteq Z$, so none lie in $A\setminus Z$; an unmatched vertex in $B\cap Z$ would itself complete an augmenting path from $U$, contradicting Berge's Lemma applied to the maximum matching $M$), and each $C$-vertex's match partner lies outside $C$ (a short case check using the alternating-path structure), giving a bijection between $C$ and a subset of $M$, so $|C|\leq|M|$. Combined with the Lemma's $|C|\geq|M|$ for any cover $C$ and matching $M$: $|C|=|M|$, and since $M$ was maximum and $C$ achieves this bound, $C$ is a minimum vertex cover. ∎

Figure 2 checks this against an independent, brute-force computation of minimum vertex cover on several random bipartite graphs — a genuinely different algorithm arriving at the same number every time, exactly as the theorem demands. Section 10 records a specific non-bipartite graph where the two quantities genuinely differ, showing bipartiteness is not a technical convenience but a load-bearing hypothesis.

Scatter plot of maximum matching size (circles) and brute-force minimum vertex cover size (crosses) for 18 random bipartite graphs, with every circle and cross exactly overlapping.
Figure — Every trial: matching size exactly equals cover size. Across $18$ random bipartite graphs of varying size and density, an augmenting-path maximum matching algorithm and an independent brute-force minimum vertex cover search agree exactly, every time — the circles and crosses coincide at every single trial, Section 6's theorem holding with no exceptions across the entire sample.

7. Hall's Marriage Theorem

Theorem (Hall)

A bipartite graph $G=(A\cup B,E)$ has a matching saturating every vertex of $A$ iff $|N(S)|\geq|S|$ for every $S\subseteq A$ (Hall's condition), where $N(S)$ is the set of $B$-vertices adjacent to some vertex of $S$.

Proof. ($\Rightarrow$) A saturating matching sends each $S\subseteq A$ to $|S|$ distinct partners, all lying in $N(S)$, so $|N(S)|\geq|S|$. ($\Leftarrow$) Suppose Hall's condition holds but no saturating matching exists. Let $M$ be a maximum matching, so $|M|<|A|$; by König's theorem (Section 6), a minimum vertex cover $C=C_A\cup C_B$ ($C_A\subseteq A$, $C_B\subseteq B$) also has size $|M|<|A|$. Since $C$ covers every edge, no edge runs from $A\setminus C_A$ to $B\setminus C_B$, i.e. $N(A\setminus C_A)\subseteq C_B$, so $|N(A\setminus C_A)|\leq|C_B|$. Hall's condition applied to $S=A\setminus C_A$ gives $|N(A\setminus C_A)|\geq|A\setminus C_A|=|A|-|C_A|$. Chaining: $|A|-|C_A|\leq|C_B|$, i.e. $|A|\leq|C_A|+|C_B|=|C|=|M|<|A|$ — a contradiction. ∎

Hall's theorem is König's theorem's most quoted corollary — the "marriage" framing (can every one of $|A|$ people be matched to an acceptable partner in $B$) is the same mathematical statement as the vertex-cover equality one step earlier, made to sound like a scheduling or assignment problem.

8. Eulerian circuits

Theorem

A connected graph has a closed walk using every edge exactly once (an Eulerian circuit) iff every vertex has even degree.

Proof. ($\Rightarrow$) Every time the circuit visits a vertex, it uses one incoming and one outgoing edge — two edges per visit — and every edge is used in exactly one visit somewhere along the circuit, so every vertex's total edge count (its degree) is a sum of $2$'s: even. ($\Leftarrow$) Induction on $|E|$. Since every degree is even and $\geq2$ (connectedness with $\geq1$ edge rules out degree $0$), start at any vertex and walk along unused edges; even degree guarantees that whenever the walk enters a vertex other than the start, an unused edge remains to leave by, so the walk can only get stuck back at the starting vertex — producing some closed circuit $C$. If $C$ already uses every edge, done. Otherwise, since $G$ is connected, some vertex $v$ on $C$ has an edge outside $C$; removing $C$'s edges leaves every remaining degree still even (each vertex on $C$ lost an even number — $0$ or $2$ — of its edges to $C$), so by the induction hypothesis the component of $G-E(C)$ containing $v$ has its own Eulerian circuit $C'$; splicing $C'$ into $C$ at $v$ gives a strictly larger circuit. Repeating (finitely, since $|E|$ is finite) exhausts all edges. ∎

This is the theorem behind the original 1736 Königsberg bridges problem (Euler's own): the seven-bridge city graph has vertices of odd degree, so by this theorem — stated by Euler well before "graph theory" existed as a subject — no walk crossing every bridge exactly once and returning to its start can exist, regardless of how cleverly a route is chosen.

9. Computation

The figures above are generated by graph-theory/generate_figures.py. The snippet below reproduces the Euler's-formula construction trace and the König's-theorem cross-check.

history, coords, edges = build_triangulation(12, seed=1)
for n, m, f in history[::3]:
    print(n, m, f, n - m + f)

rng = random.Random(0)
for t in range(6):
    nA, nB = rng.randint(3, 6), rng.randint(3, 6)
    p = rng.uniform(0.25, 0.6)
    edges = random_bipartite(nA, nB, p, seed=t)
    mm = max_matching(nA, edges)
    vc = brute_force_min_vertex_cover(nA, nB, edges)
    print(f"trial {t}: nA={nA} nB={nB} |E|={len(edges)}  matching={mm}  vertex_cover={vc}  equal={mm==vc}")

Actual output:

3 3 2 2
6 12 8 2
9 21 14 2
12 30 20 2
15 39 26 2

trial 0: nA=6 nB=6 |E|=5   matching=3  vertex_cover=3  equal=True
trial 1: nA=6 nB=6 |E|=26  matching=6  vertex_cover=6  equal=True
trial 2: nA=5 nB=6 |E|=10  matching=4  vertex_cover=4  equal=True
trial 3: nA=4 nB=4 |E|=6   matching=4  vertex_cover=4  equal=True
trial 4: nA=3 nB=5 |E|=12  matching=3  vertex_cover=3  equal=True
trial 5: nA=4 nB=5 |E|=6   matching=3  vertex_cover=3  equal=True

Every triangulation step preserves $n-m+f=2$ exactly, and every one of the six random bipartite trials confirms matching size $=$ vertex cover size exactly — two independent algorithms (an augmenting-path search and brute-force subset enumeration) landing on the same number every time, precisely what König's theorem promises.

10. Common pitfalls

Pitfall — the Five and Four Color Theorems are proved by genuinely different means

Section 5's proof is fully checkable by hand and was, within a few years of Kempe's original (flawed) four-color attempt. The Four Color Theorem's only known proofs rely on a computer-checked case analysis too large for direct human verification — a real and still-debated methodological question about what counts as a mathematical proof, not a gap anyone expects to close by finding a short hand argument (many have tried and failed for over a century).

Pitfall — König's theorem genuinely requires bipartiteness

The $5$-cycle $C_5$ has maximum matching size $2$ (any two disjoint edges) but minimum vertex cover size $3$ (removing any $2$ vertices from a $5$-cycle always leaves at least one edge uncovered, checkable by exhausting the $\binom52=10$ pairs). Section 6's Lemma ($\leq$) still holds, but equality fails outside bipartite graphs — the harder direction of the proof used the two-sided structure ($A$ vs. $B$) essentially, via the alternating-path argument.

Pitfall — a graph having $n-1$ edges does not by itself make it a tree

Section 2's theorem needs either connectivity or acyclicity as a second hypothesis alongside the edge count — not the count alone. Two disjoint triangles plus an isolated edge (total $8$ vertices, $7$ edges $=n-1$) has the right edge count but is neither connected nor acyclic; it is not a tree, and adding the missing hypothesis is not optional bookkeeping.

Pitfall — Euler's formula requires a connected planar embedding, both hypotheses

A disconnected planar graph with $k$ components satisfies $n-m+f=1+k$, not $2$ (each extra component adds a vertex-and-edge-free contribution to $n$ without splitting a face, until faces are shared across components in the embedding) — Section 3's proof explicitly used connectivity to guarantee a spanning structure to induct on. Non-planar graphs drawn with crossings simply have no well-defined face count consistent with the formula at all; "planar" is doing real work, not just describing a convenient special case.

11. Connections

12. References