Graph theory studies the combinatorial structure of networks through vertices and edges, asking fundamental questions about connectivity, colouring, and extremal properties. This course develops the core theory underlying modern combinatorics, beginning with essential objects like trees and planar graphs before advancing to deep structural results. The Cambridge II curriculum emphasises three interconnected themes: min-max duality (where upper and lower bounds on graph properties meet in equilibrium), the probabilistic method (where existence proofs avoid explicit construction), and the surprising power of algebraic invariants in capturing combinatorial phenomena.

The course progresses from local to global understanding. Early chapters establish foundations: how connectivity and matching relate through Hall's theorem and Menger's theorem, and how the chromatic number — a fundamental measure of graph structure — appears across colouring, extremal theory, and random graph models. The extremal results of Chapter 4 answer the question "how many edges can a graph have while avoiding a given subgraph," a line of inquiry culminating in Turán's theorem and feeding directly into Ramsey theory. Chapters 5 and 6 reveal the probabilistic method as a tool for proving existence results that constructive approaches cannot reach, yielding both Ramsey numbers and the surprising fact that random graphs can simultaneously have large girth and chromatic number.

The final chapter reframes graph theory through linear algebra and spectral methods, showing that eigenvalues of the adjacency matrix encode deep information about graph structure. This algebraic perspective not only unifies earlier results but opens connections to geometry and algebra that extend far beyond the combinatorial plane. Throughout, the course demonstrates how the same graph-theoretic objects — trees, colourings, dense subgraphs — appear across vastly different contexts, each yielding new insights into what makes a graph "typical," "extremal," or "structured."

# 1. Introduction

This chapter lays the combinatorial foundations of graph theory. We introduce the basic objects — graphs, their substructures, and the structural properties that distinguish them — and study three fundamental classes: trees, bipartite graphs, and planar graphs. The central questions are: what does connectivity look like locally and globally, how do acyclic structures characterise spanning subgraphs, and what constraints does planarity impose on edge counts?

## Basic Definitions and Graph Families

[motivation] ### Why graphs? Many problems in combinatorics, computer science, and geometry reduce to questions about pairwise relationships between objects. A graph is the minimal abstraction capturing exactly this: a set of objects (vertices) and a set of pairs (edges). By stripping away everything except the adjacency structure, graph theory isolates the combinatorial essence of connectivity, reachability, and layout problems. The power of the abstraction lies in what it ignores. A graph does not know about the physical positions of its vertices, the lengths of its edges, or any weighting. Two graphs are the same combinatorial object if there is a bijection between their vertex sets preserving adjacency — a graph isomorphism. This means we study structure, not representation. [/motivation]

We fix some notation that will be used throughout the course. Write $[n] = \{1, \ldots, n\}$ for the set of the first $n$ positive integers. For a set $X$ and $k \in \mathbb{N}$, write $X^{(k)} = \{Y \subseteq X \mid |Y| = k\}$ for the collection of all $k$-element subsets of $X$.

[definition: Graph] A **graph** is a pair $G = (V, E)$, where $V$ is a set of **vertices** and $E \subseteq V^{(2)}$ is a set of **edges** — that is, $E$ is a collection of 2-element subsets of $V$. We write $V(G)$ for the vertex set and $E(G)$ for the edge set. The **order** of $G$ is $|G| = |V(G)|$, and the **size** is $e(G) = |E(G)|$. [/definition]

Edges are unordered pairs: $\{u, v\} = \{v, u\}$. There are no loops (edges from a vertex to itself) and no multiple edges between the same pair of vertices — this is a **simple** graph. We sometimes write $uv$ as shorthand for the edge $\{u, v\}$, so for instance $13$ denotes the edge $\{1, 3\}$. Most graphs in this course are finite, meaning $|V(G)|$ is finite.

Before listing families, we note that $K_3$ and $C_3$ are the same graph by definition — the cycle $C_3$ is the complete graph $K_3$. This is a first sign that the same combinatorial object can arise through different constructions, and that what matters is the adjacency structure, not the label attached to it. The formal notion making this precise is graph isomorphism, defined below.

The following families serve as running examples and benchmarks throughout the course. Their names encode specific structural features that we will recognise again and again.

**Complete graph $K_n$**: the graph with $V = [n]$ and $E = V^{(2)}$, so every pair of vertices is joined by an edge. It has $\binom{n}{2}$ edges. The complete graph is the densest simple graph on $n$ vertices.

**Empty graph $\overline{K}_n$**: the graph with $V = [n]$ and $E = \varnothing$. No two vertices are adjacent. It sits at the opposite extreme from $K_n$.

**Path $P_n$**: the graph with vertex set $V = [n+1]$ and edge set $E = \{\{1,2\}, \{2,3\}, \ldots, \{n, n+1\}\}$. It has $n$ edges connecting $n+1$ vertices in a line. Paths are the simplest trees; they will appear as the extremal case in several results.

**Cycle $C_n$**: the graph with vertex set $V = [n]$ and edge set $E = \{\{1,2\}, \{2,3\}, \ldots, \{n-1,n\}, \{n,1\}\}$. It has $n$ vertices and $n$ edges forming a closed loop. Even and odd cycles behave very differently — odd cycles are the fundamental obstruction to bipartiteness.

These four families are not merely illustrations: $K_n$ maximises edges, $P_n$ and $C_n$ are the simplest connected and cyclic structures, and their parity (even vs. odd) turns out to govern deep properties of the graphs that contain them.

[definition: Neighbourhood and Degree] Let $G$ be a graph and $x \in V(G)$. The **neighbourhood** of $x$ in $G$ is \begin{align*} N_G(x) = \{y \in V(G) \mid \{x, y\} \in E(G)\}. \end{align*} If $y \in N_G(x)$, we say $x$ and $y$ are **adjacent** and write $x \sim y$. The **degree** function is the map $\deg: V(G) \to \mathbb{N}$ assigning to each vertex $x$ the size of its neighbourhood: $\deg(x) = |N_G(x)|$. We write $\delta(G)$ for the minimum degree and $\Delta(G)$ for the maximum degree of $G$. [/definition]

Note that $\sim$ is irreflexive ($x \not\sim x$ since there are no loops) and symmetric, but not transitive in general — adjacency does not propagate along paths.

Once we have a language for individual graphs and their local structure, a natural organising question arises: when should we regard two graphs as being "really the same"? The vertex labels are arbitrary — any two drawings of what we would informally call "the same graph" differ only in how the vertices happen to be named. To make this idea precise, we need a bijection between vertex sets that preserves the adjacency relation. This leads to the central notion of graph isomorphism, which underpins the rest of the course: statements about graphs are always statements about isomorphism classes, never about particular labellings.