# Lecture 10. Graph theory — basics

## Overview

A **graph** is a mathematical model of a collection of objects together with the
pairwise connections between them. The objects are drawn as dots and the
connections as lines, which makes graphs one of the most visual — and most widely
applicable — structures in discrete mathematics. Computer networks, road maps,
web-page link structures, molecule diagrams, task-dependency charts, and social
networks are all naturally described by graphs.

This lecture builds the vocabulary of graph theory from the ground up. We define
graphs and directed graphs, fix the core terminology (adjacency, incidence,
degree, loops, parallel edges, the Handshaking Lemma), catalogue the special
families we reuse constantly (null, complete, complete bipartite), and give two
matrix representations (adjacency and incidence). We then formalise movement
through a graph — walks, trails, paths, circuits, cycles — touch on
connectivity, and finish with three structural questions: when are two graphs
*the same* (isomorphism), when can a graph be drawn without crossings
(planarity and Kuratowski's theorem), and how few colours suffice to colour it
(chromatic number and index).

What separates this chapter from a bare glossary is **proof**. Almost every claim
below — the Handshaking Lemma, the edge counts of $K_n$ and $K_{m,n}$, the fact
that matrix powers count walks, Euler's formula, the non-planarity of $K_5$ and
$K_{3,3}$ — is stated as a theorem and *proved*. Learning to read and reproduce
these proofs is the real content of the course; the definitions are only the
alphabet.

Concrete **algorithms** for graphs — breadth- and depth-first search, shortest
paths, minimum spanning trees, and greedy colouring — are the subject of
**Lecture 11**, while special families such as **trees**, together with **Euler and
Hamilton tours**, are studied in **Lecture 12**. Here we build only the language and
its theory. Directed graphs reappear as the transition diagrams of finite automata
in **Lecture 14**.

Throughout the lecture we reuse one **running example**:

$$
G = (V, E), \quad V = \{a,b,c,d,e\}, \quad E = \{ab,\; ac,\; ad,\; bc,\; ce,\; de\}.
$$

![The running graph G = (V, E) with vertices a, b, c, d, e and six edges](img/l10_graph_ex.png)

## 10.1 A historical note: the bridges of Königsberg

Graph theory has a precise birthday. In 1736 Leonhard Euler settled a puzzle about
the Prussian city of Königsberg (today Kaliningrad), which straddled the river
Pregel around two islands connected to the banks and to each other by **seven
bridges**. The townspeople asked: can one take a stroll that crosses every bridge
**exactly once** and returns home?

![Königsberg multigraph: four landmasses joined by seven bridges](img/l10_konigsberg.png)

Euler's insight was to throw away all geometric detail. The four landmasses become
four **vertices**; each bridge becomes an **edge** joining the two masses it
connects. The question is now purely combinatorial: does this graph admit a closed
walk using every edge exactly once (what we now call an **Eulerian circuit**)?
Euler observed that whenever such a walk enters a landmass by one bridge it must
leave by another, so every vertex must have **even degree**. In Königsberg the
four vertices had degrees $3,3,3,5$ — all odd. Since

$$
3+3+3+5 = 14 = 2\cdot 7 = 2\lvert E\rvert,
$$

the degrees obey the Handshaking Lemma of §10.4 (their sum is twice the number of
bridges), yet *four* of them are odd, and no walk of the desired kind can exist.

Two things make this the founding example of the subject. First, it abstracts a
concrete situation into vertices and edges — the modelling move we repeat
constantly. Second, its solution turns on a **degree condition**, exactly the kind
of counting argument this chapter develops. The systematic theory of Eulerian
circuits and their construction belongs to Lecture 12; here Königsberg motivates
why *degrees* and their *parities* are worth studying so carefully.

## 10.2 Graphs and directed graphs

A **graph** $G = (V, E)$ consists of a non-empty set $V$ of **vertices** (also
called *nodes* or *points*) and a set $E$ of **edges** (also *lines*), where each
edge joins an **unordered** pair of vertices. We write $|V|$ for the number of
vertices (the **order** of the graph) and $|E|$ for the number of edges (the
**size**). An edge joining vertices $u$ and $v$ is written $uv$ or $\{u,v\}$;
because the pair is unordered, $uv$ and $vu$ denote the same edge.

Commentary: the whole of the graph lives in the pair $(V,E)$; the *drawing* is a
convenience for humans, and — as isomorphism (§10.10) will make precise — the same
graph has infinitely many drawings. Two vertices are joined or they are not; how
long or curved the line is carries no information (until we add weights in §10.7).

A **simple graph** has no loops and no parallel edges (both defined in §10.3);
unless stated otherwise, "graph" means "simple graph". Formally, in a simple graph
$E$ is a set of $2$-element subsets of $V$. A graph that *does* allow parallel
edges (so that $E$ is a **multiset**) is a **multigraph**.

A **directed graph** (or **digraph**) $D = (V, A)$ replaces edges by **arcs**
(directed edges): each arc is an **ordered** pair $(u,v)$, drawn as an arrow from
the **tail** $u$ to the **head** $v$. Now $(u,v)$ and $(v,u)$ are *different*
arcs — direction matters. Digraphs model one-way relationships: one-way streets,
web hyperlinks (page $u$ links to page $v$), prerequisite chains, task
dependencies, or the transitions of a finite automaton (Lecture 14).

**Example.** The running graph $G$ is undirected: the edge $ac$ means $a$ and $c$
are mutually connected. If instead we modelled a one-way street network we might
write the arc $(a,c)$ to mean "you may drive from $a$ to $c$ but not back", and we
would need a separate arc $(c,a)$ to allow the return trip.

**Remark (why "non-empty" $V$).** We require $V \neq \varnothing$ purely to avoid
degenerate special-casing; some authors permit the empty graph. Nothing in this
chapter depends on the choice.

![The same five vertices drawn twice: as an undirected graph with plain edges, and as a directed graph with arrows](img/l10_graph_digraph.png)

## 10.3 Core terminology

Fix a graph $G=(V,E)$.

- **Adjacency.** Two vertices $u,v$ are **adjacent** (are **neighbours**) if
  $uv \in E$. The set of neighbours of $v$ is its **neighbourhood** $N(v)$, and
  $|N(v)|$ is its size.
- **Incidence.** A vertex $v$ and an edge $e$ are **incident** if $v$ is one of the
  two endpoints of $e$. Two edges are **adjacent** if they share an endpoint.
- **Loop.** A **loop** is an edge that joins a vertex to itself, i.e. an edge $vv$.
  Simple graphs contain no loops.
- **Parallel (multiple) edges.** Two or more edges joining the *same* pair of
  vertices are **parallel edges**. Simple graphs contain none; multigraphs may.
- **Vertex degree.** The **degree** $\deg(v)$ of a vertex $v$ is the number of
  edges incident with it, where a loop counts **twice**. A vertex of degree $0$ is
  an **isolated vertex** (it has no neighbours); a vertex of degree $1$ is a
  **pendant** (or *leaf*). In a simple graph $\deg(v) = |N(v)|$.
- **Maximum and minimum degree.** We write $\Delta(G) = \max_v \deg(v)$ and
  $\delta(G) = \min_v \deg(v)$. A graph is **$r$-regular** if every vertex has the
  same degree $r$ (so $\Delta = \delta = r$).
- **Degree sequence.** The list of all vertex degrees, usually written in
  non-increasing order.
- **Subgraph.** $H = (V', E')$ is a **subgraph** of $G$ if $V'\subseteq V$,
  $E'\subseteq E$, and every edge of $E'$ has both endpoints in $V'$. It is an
  **induced subgraph** on $V'$ if $E'$ is *all* edges of $G$ with both ends in
  $V'$.

For a **digraph**, degree splits in two: the **out-degree** $\deg^{+}(v)$ is the
number of arcs with tail $v$ (arrows leaving $v$), and the **in-degree**
$\deg^{-}(v)$ is the number of arcs with head $v$ (arrows entering $v$).

**Common pitfall (loops and degree).** The "a loop counts twice" convention is not
arbitrary: it is exactly what keeps the Handshaking Lemma (§10.4) true, because a
loop at $v$ is incident to $v$ at *both* of its ends. Forgetting this is the single
most common error in degree computations for multigraphs. In simple graphs the
issue never arises, since loops are forbidden.

## 10.4 The Handshaking Lemma

The most fundamental counting fact about graphs relates the *local* data of
degrees to the *global* count of edges.

![Handshaking Lemma on graph G: sum of degrees = 12 = 2 times 6 = 2|E|](img/l10_handshaking.png)

**Theorem 10.1 (Handshaking Lemma).** In any graph (simple or multi),

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

*Proof.* We count in two ways the set

$$
I = \{(v,e) : v \in V,\ e \in E,\ v \text{ is incident with } e\}
$$

of **incidences** — vertex–edge pairs in which the vertex is an endpoint of the
edge. This is the classic *double-counting* technique.

Count by vertices. Group the incidences by their first coordinate. A fixed vertex
$v$ appears in exactly $\deg(v)$ incidences, one for each edge at $v$ (a loop at
$v$ produces two incidences $(v, e)$ — one for each end — matching the "counts
twice" convention). Hence

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

Count by edges. Group the incidences by their second coordinate. A fixed edge $e$
has exactly two endpoints, so it appears in exactly two incidences (for a loop,
the two endpoints coincide but the two incidences are still counted). Hence

$$
|I| = \sum_{e \in E} 2 = 2\,|E|.
$$

Equating the two expressions for the same quantity $|I|$ gives
$\sum_{v}\deg(v) = 2|E|$. $\blacksquare$

The lemma is often phrased for a party: **the total number of hands shaken (summed
over people) is twice the number of handshakes**, since each handshake involves two
hands. Its most-used consequence is a parity statement.

**Corollary 10.2 (odd-degree vertices).** In any graph, the number of vertices of
odd degree is even.

*Proof.* Partition the vertices by the parity of their degree:

$$
V_o = \{v : \deg(v)\text{ odd}\}, \qquad V_e = \{v : \deg(v)\text{ even}\}.
$$

By Theorem 10.1,

$$
\sum_{v\in V_o}\deg(v) \;+\; \sum_{v\in V_e}\deg(v) \;=\; 2|E|.
$$

The right-hand side is even. The sum $\sum_{v\in V_e}\deg(v)$ is a sum of even
numbers, hence even. Subtracting, $\sum_{v\in V_o}\deg(v)$ is even. But this is a
sum of $|V_o|$ odd numbers, and modulo $2$ each odd number is $\equiv 1$, so

$$
\sum_{v\in V_o}\deg(v) \equiv |V_o| \pmod 2.
$$

Thus $|V_o|$ is even. $\blacksquare$

**Remark.** What rules out the Königsberg walk (§10.1) is the **even-degree
condition** for an Eulerian circuit: a closed walk that uses every edge exactly
once must pair the edges at each vertex into an entry and an exit, so *every*
vertex must have **even** degree. Königsberg's graph has four odd-degree vertices,
violating this, so no such walk exists. Note that Corollary 10.2 is *not* violated
here — four is an *even* number of odd-degree vertices, so the graph is perfectly
consistent; the obstruction is the even-degree requirement itself, not the parity
of the count of odd vertices. Corollary 10.2 does, however, instantly answer
questions like "can $7$ people each shake hands with exactly $3$ others?" — no,
because that would be $7$ vertices of odd degree $3$, an odd count.

**Proposition 10.3 (directed handshaking).** In any digraph $D=(V,A)$,

$$
\sum_{v\in V}\deg^{+}(v) \;=\; \sum_{v\in V}\deg^{-}(v) \;=\; |A|.
$$

*Proof.* Every arc $(u,w)$ has exactly one tail $u$ and one head $w$. Summing
out-degrees counts each arc once, at its tail; summing in-degrees counts each arc
once, at its head. Both totals therefore equal the number of arcs, $|A|$.
$\blacksquare$

A second, less obvious counting consequence uses the **pigeonhole principle**
(Lecture 8).

**Proposition 10.4 (two vertices of equal degree).** Every simple graph with
$n \ge 2$ vertices has two distinct vertices of the same degree.

*Proof.* In a simple graph each degree lies in $\{0,1,\dots,n-1\}$, a set of $n$
possible values. Suppose, for contradiction, that all $n$ vertices had *distinct*
degrees; then every value $0,1,\dots,n-1$ would occur exactly once. In particular
some vertex $x$ has degree $0$ (isolated, adjacent to nobody) and some vertex $y$
has degree $n-1$ (adjacent to all $n-1$ other vertices, hence adjacent to $x$).
This contradicts $x$ being isolated. So not all values can occur, leaving at most
$n-1$ distinct degrees for $n$ vertices; by pigeonhole two vertices coincide in
degree. $\blacksquare$

**Example (degrees and Handshaking in $G$).** In the running graph $G$:

| vertex | incident edges | $\deg$ |
|:------:|:---------------|:------:|
| $a$ | $ab, ac, ad$ | $3$ |
| $b$ | $ab, bc$ | $2$ |
| $c$ | $ac, bc, ce$ | $3$ |
| $d$ | $ad, de$ | $2$ |
| $e$ | $ce, de$ | $2$ |

The degree sequence is $(3,3,2,2,2)$, whose sum is $3+3+2+2+2 = 12$. Indeed
$12 = 2\cdot 6 = 2|E|$, confirming Theorem 10.1, and $G$ has exactly two odd-degree
vertices ($a$ and $c$) — an even count, as Corollary 10.2 requires. There are no
isolated vertices, and (illustrating Proposition 10.4) the degree $2$ repeats three
times.

**Example (digraph degrees).** Take the digraph on $\{1,2,3\}$ with arcs
$(1,2),(1,3),(2,3),(3,1)$. Then $\deg^{+}(1)=2,\ \deg^{-}(1)=1$;
$\deg^{+}(2)=1,\ \deg^{-}(2)=1$; $\deg^{+}(3)=1,\ \deg^{-}(3)=2$. The out-degrees
sum to $4$, the in-degrees sum to $4$, and $|A| = 4$, illustrating
Proposition 10.3.

## 10.5 Special families of graphs

Certain graphs recur so often that they have standard names and formulas.

- **Null (empty) graph $N_n$.** The graph on $n$ vertices with **no edges** at all:
  $E=\varnothing$. Every vertex is isolated and $|E|=0$. It is $0$-regular.
- **Path $P_n$.** $n$ vertices $v_1,\dots,v_n$ in a line with edges
  $v_1v_2, v_2v_3, \dots, v_{n-1}v_n$; it has $n-1$ edges, two pendants (the ends),
  and all interior vertices of degree $2$.
- **Cycle $C_n$** ($n\ge 3$). $n$ vertices arranged in a ring: edges
  $v_1v_2,\dots,v_{n-1}v_n,v_nv_1$. It has $n$ edges and is $2$-regular.
- **Complete graph $K_n$.** A simple graph on $n$ vertices in which **every** pair
  of distinct vertices is joined by an edge. It is $(n-1)$-regular.
- **Complete bipartite graph $K_{m,n}$.** The vertex set splits into two disjoint
  **parts** $X$ ($m$ vertices) and $Y$ ($n$ vertices); every vertex of $X$ is
  joined to every vertex of $Y$, and there are **no** edges inside a part. A graph
  whose vertices split into two such edge-free parts is **bipartite**; $K_{m,n}$ is
  the largest bipartite graph on those parts. The special case $K_{1,n}$ is a
  **star**.

**Theorem 10.5 (edge counts).**

$$
|E(N_n)| = 0, \qquad |E(K_n)| = \binom{n}{2} = \frac{n(n-1)}{2}, \qquad |E(K_{m,n})| = mn.
$$

*Proof.* $N_n$ has no edges by definition.

For $K_n$ we give two proofs. *(i) Bijective.* In a simple graph an edge is a
$2$-element subset of $V$; in $K_n$ **every** such subset is present, so the edges
are in bijection with the $2$-subsets of an $n$-set, of which there are
$\binom{n}{2}$. *(ii) Via Handshaking.* Every vertex of $K_n$ has degree $n-1$, so
by Theorem 10.1,

$$
2|E| = \sum_{v}\deg(v) = n(n-1), \qquad\text{hence}\qquad |E| = \frac{n(n-1)}{2} = \binom{n}{2}.
$$

For $K_{m,n}$, group the edges by their endpoint in $X$. Each of the $m$ vertices
of $X$ is joined to all $n$ vertices of $Y$ and to no others, contributing exactly
$n$ edges, and no edge is counted twice (each edge has exactly one endpoint in
$X$). Hence $|E| = m\cdot n$. Equivalently, by Handshaking every vertex of $X$ has
degree $n$ and every vertex of $Y$ has degree $m$, so
$2|E| = mn + nm = 2mn$. $\blacksquare$

**Theorem 10.6 (maximum size of a simple graph).** A simple graph on $n$ vertices
has at most $\binom{n}{2}$ edges, with equality **iff** it is $K_n$.

*Proof.* Its edge set is a set of distinct $2$-subsets of the $n$-element set $V$
(distinct because there are no parallel edges; $2$-subsets because there are no
loops). There are only $\binom{n}{2}$ such subsets in all, so
$|E| \le \binom{n}{2}$. Equality holds iff *every* $2$-subset is an edge, which is
precisely the definition of $K_n$. $\blacksquare$

**Example.** A round-robin tournament among $5$ players, where everyone plays
everyone once, is modelled by $K_5$: $\binom{5}{2} = 10$ games. A recommendation
setting with $3$ users each able to rate any of $4$ movies is modelled by
$K_{3,4}$: $3 \cdot 4 = 12$ possible user–movie edges, and no user–user or
movie–movie edges. Numerically, $K_3$ (a triangle) has $3$ edges, $K_4$ has $6$,
$K_5$ has $10$, and $K_6$ has $15$.

**Remark (density).** Theorem 10.6 says a simple graph has $O(n^2)$ edges. A graph
with $\Theta(n^2)$ edges is called **dense**; one with $O(n)$ edges is **sparse**.
The distinction drives the choice of data structure in Lecture 11: adjacency
matrices favour dense graphs, adjacency lists favour sparse ones.

![Three special graph families: the empty graph N₄ (0 edges), the complete graph K₄ (6 edges), and the complete bipartite graph K₃,₃ (9 edges)](img/l10_families.png)

## 10.6 Matrix representations

Graphs are convenient for humans to draw, but a computer needs a numeric encoding.
The two standard ones are the adjacency matrix and the incidence matrix.

### Adjacency matrix

The **adjacency matrix** $A = [a_{ij}]$ of a graph on vertices $v_1,\dots,v_n$ is
the $n \times n$ matrix with

$$
a_{ij} = \bigl(\text{number of edges between } v_i \text{ and } v_j\bigr).
$$

For a simple graph every entry is $0$ or $1$. Key properties: for an *undirected*
graph $A$ is **symmetric** ($a_{ij} = a_{ji}$); the diagonal is $0$ when there are
no loops (a loop at $v_i$ contributes $2$ to $a_{ii}$ in the usual convention — though
some worksheets, e.g. Practical 5, instead record the *number of loops* on the diagonal,
counting a loop once); and
the **$i$-th row sum equals $\deg(v_i)$**. For a *digraph*, $a_{ij}=1$ when the arc
$(v_i,v_j)$ is present, so $A$ need **not** be symmetric; the row sum gives
$\deg^{+}(v_i)$ and the column sum gives $\deg^{-}(v_j)$.

![Adjacency matrix of the running graph G, symmetric with zero diagonal](img/l10_adj_matrix.png)

**Example.** Ordering the vertices $a,b,c,d,e$, the adjacency matrix of the running
graph $G$ is:

|       | $a$ | $b$ | $c$ | $d$ | $e$ |
|:-----:|:---:|:---:|:---:|:---:|:---:|
| $a$   | 0   | 1   | 1   | 1   | 0   |
| $b$   | 1   | 0   | 1   | 0   | 0   |
| $c$   | 1   | 1   | 0   | 0   | 1   |
| $d$   | 1   | 0   | 0   | 0   | 1   |
| $e$   | 0   | 0   | 1   | 1   | 0   |

It is symmetric across the diagonal, the diagonal is all $0$ (no loops), and the
row sums $3,2,3,2,2$ reproduce the degree sequence found earlier.

### What the powers of $A$ count

The single most useful algebraic property of the adjacency matrix is that its
*powers* count walks. As defined in §10.8, a **walk of length $k$** from $v_i$ to
$v_j$ is a sequence of $k$ edges $v_i\!=\!u_0,u_1,\dots,u_k\!=\!v_j$ with each
consecutive pair adjacent; vertices and edges may repeat.

**Theorem 10.7 (walk counting).** Let $A$ be the adjacency matrix of a graph
(directed or undirected) on $v_1,\dots,v_n$. For every integer $k\ge 0$, the
$(i,j)$ entry of $A^k$ equals the number of walks of length $k$ from $v_i$ to
$v_j$.

*Proof.* By induction on $k$.

*Base $k=0$.* We take $A^0 = I$, the identity. A walk of length $0$ is a single
vertex with no edges; there is exactly one such walk from $v_i$ to $v_j$ when
$i=j$ (the trivial walk) and none when $i\neq j$. This matches $I_{ij}$, which is
$1$ if $i=j$ and $0$ otherwise. (The case $k=1$ is also immediate: $A^1=A$, and
$a_{ij}$ is by definition the number of length-$1$ walks — i.e. edges — from $v_i$
to $v_j$.)

*Inductive step.* Assume the claim for some $k\ge 0$: $(A^k)_{i\ell}$ is the number
of walks of length $k$ from $v_i$ to $v_\ell$, for all $i,\ell$. Since
$A^{k+1} = A^k A$, the definition of matrix product gives

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

Interpret the right-hand side combinatorially. Every walk of length $k+1$ from
$v_i$ to $v_j$ is obtained **uniquely** by taking a walk of length $k$ from $v_i$
to some vertex $v_\ell$ and then appending one edge from $v_\ell$ to $v_j$; the
vertex $v_\ell$ is exactly the second-to-last vertex of the walk. Conversely each
such pair (a length-$k$ walk to $v_\ell$, plus an edge $v_\ell v_j$) yields a
distinct length-$(k+1)$ walk. So, summing over the possible $v_\ell$,

$$
\#\{\text{length-}(k{+}1)\text{ walks } v_i\!\to\! v_j\} = \sum_{\ell=1}^n \bigl(\#\{\text{length-}k\text{ walks } v_i\!\to\! v_\ell\}\bigr) \cdot a_{\ell j} = \sum_{\ell=1}^n (A^k)_{i\ell}\, a_{\ell j},
$$

using the induction hypothesis in the last step and the fact that $a_{\ell j}$ is
the number of edges (length-$1$ walks) from $v_\ell$ to $v_j$. This equals
$(A^{k+1})_{ij}$, completing the induction. $\blacksquare$

**Example.** Squaring the adjacency matrix of $G$ gives

|       | $a$ | $b$ | $c$ | $d$ | $e$ |
|:-----:|:---:|:---:|:---:|:---:|:---:|
| $a$   | 3   | 1   | 1   | 0   | 2   |
| $b$   | 1   | 2   | 1   | 1   | 1   |
| $c$   | 1   | 1   | 3   | 2   | 0   |
| $d$   | 0   | 1   | 2   | 2   | 0   |
| $e$   | 2   | 1   | 0   | 0   | 2   |

Reading off entries of $A^2$:

- $(A^2)_{ae}=2$: there are two walks of length $2$ from $a$ to $e$, namely
  $a\text{–}c\text{–}e$ and $a\text{–}d\text{–}e$.
- $(A^2)_{ad}=0$: no length-$2$ walk from $a$ to $d$ (their neighbourhoods
  $\{b,c,d\}$ and $\{a,e\}$ are disjoint), even though $ad$ is an edge (a length-$1$
  walk).
- The **diagonal** entries $3,2,3,2,2$ equal the degrees. This is no accident: a
  closed walk of length $2$ from $v$ goes to a neighbour and back, so
  $(A^2)_{vv} = \deg(v)$ in a simple graph.

**Remark (counting triangles).** By the same theorem the diagonal of $A^3$ counts
closed walks of length $3$. Each such walk is a triangle traversed from one of its
three vertices in one of two directions, so $(A^3)_{vv}$ is twice the number of
triangles through $v$, and

$$
\operatorname{trace}(A^3) = \sum_v (A^3)_{vv} = 6\cdot(\text{number of triangles}).
$$

For $G$ one computes $\operatorname{trace}(A^3)=6$, correctly detecting its single
triangle $a\text{–}b\text{–}c$. This is the theoretical basis of matrix-based
triangle-counting used in network analysis.

**Common pitfall.** $A^k$ counts **walks**, not paths or trails — repeated
vertices and edges are allowed. Counting *paths* of a given length is a much harder
problem (no simple matrix formula), and conflating the two is a frequent error.

### Incidence matrix

The **incidence matrix** $M = [m_{ij}]$ has one row per vertex and one column per
edge; $m_{ij} = 1$ if vertex $v_i$ is an endpoint of edge $e_j$, and $0$ otherwise.
In a simple graph **every column has exactly two $1$s** (an edge has two
endpoints), and the **$i$-th row sum equals $\deg(v_i)$** again. A loop is the
exceptional case, encoded by a single $2$ in its column.

**Example.** Label the edges $e_1=ab,\ e_2=ac,\ e_3=ad,\ e_4=bc,\ e_5=ce,\ e_6=de$. The incidence matrix of $G$ is:

|       | $e_1$ | $e_2$ | $e_3$ | $e_4$ | $e_5$ | $e_6$ |
|:-----:|:-----:|:-----:|:-----:|:-----:|:-----:|:-----:|
| $a$   | 1     | 1     | 1     | 0     | 0     | 0     |
| $b$   | 1     | 0     | 0     | 1     | 0     | 0     |
| $c$   | 0     | 1     | 0     | 1     | 1     | 0     |
| $d$   | 0     | 0     | 1     | 0     | 0     | 1     |
| $e$   | 0     | 0     | 0     | 0     | 1     | 1     |

Each column sums to $2$ (illustrating the Handshaking double count column by
column: summing all entries gives $2|E| = 12 = \sum_v\deg(v)$), and the row sums
$3,2,3,2,2$ are once more the degrees.

**Remark (which representation?).** The adjacency matrix is compact ($n\times n$)
and answers "are $u,v$ adjacent?" in $O(1)$; the incidence matrix ($n\times|E|$)
records the vertex–edge structure explicitly and generalises cleanly to
multigraphs and (with $\pm 1$ entries, tail $-1$ and head $+1$) to digraphs, where
it underlies flow and circuit theory. In practice large sparse graphs are stored
as **adjacency lists** (each vertex keeps a list of its neighbours), the workhorse
representation for the algorithms of Lecture 11.

## 10.7 Weighted graphs

A **weighted graph** is a graph together with a **weight function**
$w : E \to \mathbb{R}$ assigning a number $w(e)$ — a *cost*, *length*, *capacity*,
or *time* — to each edge. (Digraphs may be weighted the same way.) The **weight of
a walk** is the sum of the weights of the edges it uses. Weighted graphs are what
make questions like "shortest route" or "cheapest network" meaningful; the
algorithms that answer them (Dijkstra, Bellman–Ford, Prim, Kruskal) belong to
Lecture 11, but the model belongs here.

In a computer we store weights by replacing the $1$s of the adjacency matrix with
the weight $w(v_iv_j)$, using a sentinel such as $\infty$ (or a separate boolean
mask) for "no edge".

**Example.** Model four cities $a,b,c,d$ with road lengths in kilometres:
$w(ab)=5,\ w(bc)=2,\ w(ac)=4,\ w(cd)=7$. The route $a \to b \to c \to d$ has
weight $5 + 2 + 7 = 14$ km, whereas $a \to c \to d$ has weight $4 + 7 = 11$ km, so
the second route is shorter even though it uses fewer edges. The **weight**, not
the number of edges, is what we minimise — a distinction that separates
"fewest hops" (unweighted shortest path, solved by breadth-first search) from
"shortest distance" (weighted shortest path, solved by Dijkstra), both in
Lecture 11.

## 10.8 Walks, trails, paths, circuits, and cycles

Movement through a graph is described by *walks*, which are then refined by
forbidding repetition of edges or vertices.

A **walk** of length $k$ is an alternating sequence of vertices and edges

$$
v_0,\, e_1,\, v_1,\, e_2,\, v_2,\, \dots,\, e_k,\, v_k,
$$

in which each edge $e_i$ joins $v_{i-1}$ and $v_i$. Its **length** is the number of
edges, $k$. In a simple graph a walk is determined by its vertex list, so we write
it as $v_0\text{–}v_1\text{–}\cdots\text{–}v_k$. The endpoints are $v_0$ (start)
and $v_k$ (end).

- A walk is **closed** if it starts and ends at the same vertex ($v_0=v_k$), and
  **open** otherwise.
- A **trail** is a walk with **no repeated edge** (vertices may repeat).
- A **path** is a walk with **no repeated vertex** (hence no repeated edge either).
- A **circuit** is a **closed trail**: it returns to its start and repeats no edge.
- A **cycle** is a **closed path**: it returns to its start and repeats no vertex
  except that final return. A cycle of length $k$ is a copy of $C_k$; the shortest
  cycle in a simple graph has length $3$ (a triangle). The length of a shortest
  cycle is the **girth**.

The containment hierarchy is: every path is a trail, and every trail is a walk;
every cycle is a circuit, and every circuit is a closed walk. The reverse
inclusions fail, as the examples below show.

![A path a to c to e to d in graph G](img/l10_walk.png)

**Example (from the running graph $G$).**

- $a\text{–}c\text{–}b\text{–}a\text{–}d$ uses edges $ac, cb, ba, ad$ — all
  distinct, so it is a **trail**; but vertex $a$ repeats, so it is **not** a path.
  Its start $a$ and end $d$ differ, so it is an **open** walk of length $4$.
- $a\text{–}c\text{–}e\text{–}d\text{–}a$ uses edges $ac, ce, ed, da$ — all
  distinct and it returns to $a$, so it is a **circuit**. No interior vertex
  repeats, so it is in fact a **cycle** of length $4$ (a $C_4$).
- $a\text{–}b\text{–}c$ never repeats a vertex, so it is a **path** (open,
  length $2$).

The next theorem is the workhorse behind every connectivity argument: whenever
vertices are joined by *any* walk, they are joined by a genuine path.

**Theorem 10.8 (walk implies path).** If a graph contains a walk from $u$ to $v$,
then it contains a path from $u$ to $v$.

*Proof.* The set of walks from $u$ to $v$ is non-empty by hypothesis, and each has
a length in $\{0,1,2,\dots\}$, so by well-ordering we may choose a walk

$$
W:\quad u=w_0,\,w_1,\,\dots,\,w_k=v
$$

of **minimum** length $k$. We claim $W$ repeats no vertex, so that it is a path.
Suppose instead that $w_i = w_j$ for some $i<j$. Then

$$
W':\quad w_0,\,\dots,\,w_i,\,w_{j+1},\,\dots,\,w_k
$$

is again a walk from $u$ to $v$: the splice is legal because $w_i=w_j$ is adjacent
to $w_{j+1}$ (that edge was $w_jw_{j+1}$ in $W$). But $W'$ has length
$k-(j-i)<k$, contradicting the minimality of $W$. Hence no vertex repeats and $W$
is a path. $\blacksquare$

**Remark.** Theorem 10.8 lets us use "walk" and "path" interchangeably when we only
care about *reachability*, which is why the definition of connectivity in §10.9 can
be stated with either word.

**Example (a cycle from minimum degree).** Here is a small argument of the flavour
you will meet in the exercises: *if every vertex of a finite simple graph has
degree $\ge 2$, then the graph contains a cycle.* Take a longest path
$P: x_0\text{–}x_1\text{–}\cdots\text{–}x_\ell$. Since $\deg(x_0)\ge 2$, the vertex
$x_0$ has a neighbour $y$ other than $x_1$. If $y$ were outside $P$, we could
prepend it to get a longer path, contradicting maximality; so $y=x_j$ for some
$j\ge 2$, and $x_0\text{–}x_1\text{–}\cdots\text{–}x_j\text{–}x_0$ is a cycle.

## 10.9 Connectivity

A graph is **connected** if there is a walk (equivalently, by Theorem 10.8, a path)
between every pair of vertices; otherwise it is **disconnected** and falls apart
into maximal connected pieces called **connected components**. To make "pieces"
precise:

**Proposition 10.9 (components as equivalence classes).** Define a relation on $V$
by $u\sim v$ iff there is a walk from $u$ to $v$. Then $\sim$ is an equivalence
relation, and its classes are exactly the vertex sets of the connected components.

*Proof.* We check the three axioms (Lecture 3). *Reflexive:* the length-$0$ walk
$u$ joins $u$ to itself, so $u\sim u$. *Symmetric:* reversing a $u$–$v$ walk yields
a $v$–$u$ walk, so $u\sim v\Rightarrow v\sim u$ (edges are undirected).
*Transitive:* concatenating a $u$–$v$ walk with a $v$–$w$ walk yields a $u$–$w$
walk, so $u\sim v$ and $v\sim w\Rightarrow u\sim w$. Thus $\sim$ partitions $V$;
each class is connected (any two of its members are joined by a walk) and maximal
(no vertex outside is reachable), which is the definition of a component.
$\blacksquare$

The running graph $G$ is connected — for instance $b$ reaches $e$ via
$b\text{–}c\text{–}e$. Adding an isolated vertex $f$ would make the graph
disconnected, with two components $\{a,b,c,d,e\}$ and $\{f\}$.

**Bridges and cut vertices.** An edge whose removal increases the number of
components is a **bridge**; a vertex whose removal (with its incident edges) does
so is a **cut vertex**. In $G$, the edge $ad$ is *not* a bridge (the cycle
$a\text{–}c\text{–}e\text{–}d\text{–}a$ provides an alternate route), whereas in a
path every edge is a bridge. These notions measure how robustly a network stays
connected — directly relevant to fault-tolerant network design.

For **digraphs** one distinguishes **strong** connectivity (a *directed* path both
from $u$ to $v$ and from $v$ to $u$, for every pair) from **weak** connectivity
(the underlying undirected graph is connected). The web link graph, for example,
is at best weakly connected: you can often follow links from page $u$ to page $v$
without any return route. Systematic algorithms for finding components and testing
connectivity (BFS/DFS, Tarjan's strongly-connected-components algorithm) are
covered in Lecture 11.

## 10.10 Graph isomorphism and invariants

Two drawings can look completely different yet represent the *same* graph. We
capture "same structure" precisely.

Two graphs $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$ are **isomorphic**, written
$G_1 \cong G_2$, if there is a **bijection** $f : V_1 \to V_2$ that preserves
adjacency both ways:

$$
uv \in E_1 \iff f(u)\,f(v) \in E_2 \quad\text{for all } u,v \in V_1.
$$

Such an $f$ is an **isomorphism**. Intuitively, $f$ relabels the vertices of $G_1$
to turn it into $G_2$ without adding or deleting any edge. Isomorphism is an
equivalence relation on graphs (identity, inverse, and composition of
isomorphisms are isomorphisms), so it sorts all graphs into *isomorphism classes*;
"the" cycle $C_5$ or "the" graph $K_4$ really means one such class.

**How to argue two graphs are isomorphic:** exhibit an explicit bijection $f$ and
check that every edge of $G_1$ maps to an edge of $G_2$ and vice versa. Because $f$
is a bijection on finite vertex sets of equal size, it suffices to check that $f$
maps every edge to an edge and $|E_1|=|E_2|$ (the reverse direction then follows by
counting).

**How to argue they are *not* isomorphic:** find a **graph invariant** — a quantity
or property preserved by every isomorphism — on which the two graphs differ. If a
single invariant differs, no isomorphism can exist.

**Proposition 10.10 (degree sequence is an invariant).** If $f:G_1\to G_2$ is an
isomorphism, then $\deg_{G_1}(v)=\deg_{G_2}(f(v))$ for every vertex $v$;
consequently $G_1$ and $G_2$ have the same degree sequence.

*Proof.* Fix $v\in V_1$. The map $f$ restricts to a function from $N(v)$ to
$N(f(v))$: if $u\in N(v)$ then $uv\in E_1$, so $f(u)f(v)\in E_2$, i.e.
$f(u)\in N(f(v))$. This restriction is injective (as $f$ is) and surjective onto
$N(f(v))$ (any neighbour $w$ of $f(v)$ is $f(u)$ for the unique $u=f^{-1}(w)$, and
$f(u)f(v)\in E_2\Rightarrow uv\in E_1$). Hence $|N(v)|=|N(f(v))|$, i.e.
$\deg(v)=\deg(f(v))$. Applying $f$ to all vertices reorders the degree list without
changing it. $\blacksquare$

Other convenient invariants: the order $|V|$, the size $|E|$, the number of
connected components, the girth and the multiset of cycle lengths, the number of
triangles ($\tfrac16\operatorname{trace}(A^3)$), and whether the graph is
bipartite.

**Common pitfall.** Invariants are **necessary but not sufficient**: matching
degree sequences (or even all of the invariants above) do **not** guarantee
isomorphism. The next example makes this concrete.

**Example (isomorphic — pentagon vs. pentagram).** Draw $C_5$ once as a regular
pentagon with edges $\{12,23,34,45,51\}$ and once as a five-pointed star
(pentagram) with edges $\{13,35,52,24,41\}$. Define $f$ by

| $x$    | $1$ | $2$ | $3$ | $4$ | $5$ |
|:------:|:---:|:---:|:---:|:---:|:---:|
| $f(x)$ | $1$ | $3$ | $5$ | $2$ | $4$ |

Check each pentagon edge maps to a star edge: $\{1,2\}\!\to\!\{1,3\}$,
$\{2,3\}\!\to\!\{3,5\}$, $\{3,4\}\!\to\!\{5,2\}$, $\{4,5\}\!\to\!\{2,4\}$,
$\{5,1\}\!\to\!\{4,1\}$. All five images are star edges and $f$ is a bijection, so
the pentagon and pentagram are isomorphic — both are $C_5$.

**Example (not isomorphic — different degree sequence).** Let $G_1$ be the running
graph $G$ with degree sequence $(3,3,2,2,2)$ and $G_2 = C_5$ with degree sequence
$(2,2,2,2,2)$. Both have $5$ vertices, but $G$ has $6$ edges to $C_5$'s $5$, and
their degree sequences differ, so $G\not\cong C_5$ (either invariant alone
suffices).

**Example (not isomorphic — same degree sequence).** Consider two $2$-regular
graphs on $6$ vertices: the cycle $C_6$, and the disjoint union $C_3\cup C_3$ of
two triangles. Both have $6$ vertices, $6$ edges, and degree sequence
$(2,2,2,2,2,2)$ — every "local" invariant agrees. Yet they are **not** isomorphic:
$C_6$ is connected (one component) while $C_3\cup C_3$ has two, and isomorphism
preserves the number of components. Equivalently, $C_6$ has girth $6$ and no
triangle, whereas $C_3\cup C_3$ has girth $3$ and two triangles.

**Example (not isomorphic — both connected, same degree sequence).** There are
exactly two $3$-regular simple graphs on $6$ vertices, and this pair is the classic
warning. Both have $6$ vertices, $9$ edges, degree sequence $(3,3,3,3,3,3)$, and
both are connected:

- $K_{3,3}$ — bipartite, hence **triangle-free** (girth $4$).
- the **triangular prism** (two triangles joined by a matching, i.e. $C_3\times K_2$) — which **contains triangles** (girth $3$).

Since "number of triangles" (equivalently "is bipartite") is an invariant and the
two graphs differ on it, $K_{3,3}\not\cong$ prism, even though every degree-based
test is fooled. This is exactly why "same degree sequence" can never *prove*
isomorphism.

**Remark (the isomorphism problem).** Deciding whether two graphs are isomorphic is
a famous problem whose exact complexity is still open: no polynomial-time algorithm
is known, yet it is not known to be NP-complete either (Babai's 2016 algorithm runs
in quasipolynomial time). In practice one prunes with cheap invariants first and
searches for the bijection only when they all match.

## 10.11 Planar graphs and Euler's formula

A graph is **planar** if it can be drawn in the plane so that **no two edges
cross** (edges meet only at shared endpoints). Such a crossing-free drawing is a
**plane graph**. A plane graph divides the plane into **faces** (maximal connected
regions), including one unbounded **outer face**. The **boundary walk** of a face
traverses the edges around it; the number of edge-steps in that walk is the
**degree** of the face, where a bridge is counted **twice** (the walk runs along
both of its sides).

Note the distinction: *planar* is a property of the abstract graph (a drawing
exists); *plane* refers to a specific crossing-free drawing. A planar graph has
many plane drawings, but Euler's formula shows they all share the same face count.

**Theorem 10.11 (Euler's formula, 1750s).** For every *connected* plane graph with
$v$ vertices, $e$ edges, and $f$ faces,

$$
v - e + f = 2.
$$

*Proof.* Induction on the number of edges $e$.

*Base case $e=0$.* A connected graph with no edges has exactly one vertex, so
$v=1$. Its drawing occupies the plane with a single (outer) face, so $f=1$. Then
$v-e+f = 1-0+1 = 2$. $\checkmark$

*Inductive step.* Let $e\ge 1$ and assume the formula holds for every connected
plane graph with fewer than $e$ edges. Let $G$ be a connected plane graph with $e$
edges, $v$ vertices, $f$ faces. Two cases.

**Case 1: $G$ contains a cycle.** Pick an edge $\varepsilon$ that lies on a cycle.
A cycle drawn in the plane is a closed curve which, by the Jordan curve theorem,
separates the plane into an inside and an outside; the two sides of $\varepsilon$
therefore lie in **two different** faces. Delete $\varepsilon$. Its two adjacent
faces merge into one, so the face count drops by exactly $1$; the vertex count is
unchanged; and $G$ stays connected, because any route that used $\varepsilon$ can
instead go the other way around the cycle. The resulting plane graph $G'$ has
$v'=v$, $e'=e-1$, $f'=f-1$. By the induction hypothesis,

$$
v' - e' + f' = 2 \;\Longrightarrow\; v - (e-1) + (f-1) = 2 \;\Longrightarrow\; v - e + f = 2.
$$

**Case 2: $G$ contains no cycle** (it is a tree). A finite tree with at least one
edge has a vertex of degree $1$: follow a longest path; its final vertex $u$ has no
neighbour off the path (that would extend the path) and no second neighbour on it
(that would close a cycle), so $\deg(u)=1$. Delete $u$ and its single incident edge
$\varepsilon$. Being a bridge lying inside a single face, $\varepsilon$ borders the
*same* face on both sides, so deleting it does **not** change the face count; it
removes one vertex and one edge, and leaves $G'$ connected. Thus $v'=v-1$,
$e'=e-1$, $f'=f$. By the induction hypothesis,

$$
v' - e' + f' = 2 \;\Longrightarrow\; (v-1) - (e-1) + f = 2 \;\Longrightarrow\; v - e + f = 2.
$$

In both cases $v-e+f=2$, completing the induction. $\blacksquare$

**Remark (topological facts used).** The proof leans on two intuitively obvious but
genuinely topological facts — that a cycle separates the plane (Jordan curve
theorem) and that a bridge borders one face on both sides. A fully rigorous
treatment of these belongs to topology; at this level we take them as given, as
Rosen and West do.

**Example.** $K_4$ is planar: drawn without crossings (a triangle with a vertex in
the middle joined to all three) it has $v=4$, $e=6$, and $f=4$ (three inner
triangular regions plus the outer face), and indeed $4-6+4=2$.

![Planar drawing of K4 with four faces: V - E + F = 4 - 6 + 4 = 2](img/l10_planar.png)

The real power of Euler's formula is the **edge bounds** it forces on planar graphs,
which give a quick non-planarity test.

**Corollary 10.12 (edge bound).** In a simple connected planar graph with $v\ge 3$,

$$
e \le 3v - 6.
$$

*Proof.* Fix a plane drawing with $f$ faces. In a simple graph with $v\ge 3$ and at
least two edges, every face has degree $\ge 3$: a face of degree $1$ would need a
loop and a face of degree $2$ would need parallel edges (or the whole graph to be a
single edge, excluded by $v\ge 3$), both forbidden. Now count **edge–face
incidences**: summing the degrees of all faces counts each edge exactly twice (an
edge borders two faces, or is a bridge counted twice on the one face it touches),
so

$$
\sum_{\text{faces }F}\deg(F) = 2e.
$$

Since each of the $f$ terms is at least $3$, we get $3f \le 2e$, i.e.
$f \le \tfrac{2e}{3}$. Substitute $f = e - v + 2$ from Euler's formula:

$$
e - v + 2 \le \frac{2e}{3} \;\Longrightarrow\; 3e - 3v + 6 \le 2e \;\Longrightarrow\; e \le 3v - 6. \qquad \blacksquare
$$

**Corollary 10.13 ($K_5$ is not planar).** The complete graph $K_5$ is non-planar.

*Proof.* $K_5$ is simple and connected with $v=5$ and $e=\binom{5}{2}=10$. If it
were planar, Corollary 10.12 would give $10 = e \le 3v-6 = 3\cdot 5-6 = 9$, i.e.
$10 \le 9$ — false. Hence $K_5$ is not planar. $\blacksquare$

The bound $e\le 3v-6$ does *not* settle $K_{3,3}$, which has $v=6$, $e=9$ and
$3v-6=12\ge 9$. We need a sharper bound exploiting the absence of triangles.

**Corollary 10.14 (triangle-free bound).** In a simple connected planar graph with
$v\ge 3$ and **no triangles** (girth $\ge 4$),

$$
e \le 2v - 4.
$$

*Proof.* With no triangles, every cycle — hence every face boundary — has length
$\ge 4$, so every face has degree $\ge 4$. As before $\sum_F \deg(F)=2e$, giving
$4f \le 2e$, i.e. $f \le \tfrac{e}{2}$. Substituting $f=e-v+2$:

$$
e - v + 2 \le \frac{e}{2} \;\Longrightarrow\; \frac{e}{2} \le v - 2 \;\Longrightarrow\; e \le 2v - 4. \qquad\blacksquare
$$

**Corollary 10.15 ($K_{3,3}$ is not planar).** The complete bipartite graph
$K_{3,3}$ is non-planar.

*Proof.* $K_{3,3}$ is simple, connected, and bipartite, so it has no odd cycle and
in particular no triangle; it has $v=6$ and $e=9$. If it were planar,
Corollary 10.14 would give $9 = e \le 2v - 4 = 2\cdot 6 - 4 = 8$, i.e. $9\le 8$ —
false. Hence $K_{3,3}$ is not planar. $\blacksquare$

These two graphs are the "three utilities" puzzle ($K_{3,3}$: connect three houses
to gas, water, and electricity without crossing pipes — impossible) and the
"five mutually connected points" graph ($K_5$). Kuratowski proved they are the
*only* essential obstructions to planarity.

**Theorem 10.16 (Kuratowski, 1930).** A graph is planar **if and only if** it
contains no subgraph that is a **subdivision** of $K_5$ or of $K_{3,3}$.

Here a **subdivision** of a graph is obtained by repeatedly replacing an edge with
a path through new degree-$2$ vertices (placing extra points along an edge).
Subdividing does not change whether a graph can be drawn without crossings, so a
hidden $K_5$ or $K_{3,3}$ — even stretched out with extra vertices along its
edges — forces non-planarity, and its absence guarantees planarity. (We do not
prove Kuratowski's theorem; the "only if" direction is what Corollaries
10.13 and 10.15 establish for the two base cases, and the "if" direction is deep.) A
closely related characterisation, **Wagner's theorem**, replaces "subdivision" by
"minor".

![K₅ and K₃,₃ — the two forbidden graphs of Kuratowski's theorem, each drawn with its unavoidable edge crossings](img/l10_forbidden.png)

**Remark (CS relevance).** Planarity is not just recreational. Planar graphs can be
tested and drawn in **linear time** (Hopcroft–Tarjan), they admit small separators
enabling divide-and-conquer, and they arise directly in VLSI chip layout (wires
must not cross on a layer) and in geographic and circuit maps.

## 10.12 Graph colouring

A **proper vertex colouring** assigns a colour to each vertex so that **adjacent
vertices receive different colours**. The **chromatic number** $\chi(G)$ is the
minimum number of colours in a proper vertex colouring. Applications include
scheduling (colours = time slots, edges = conflicts, so a proper colouring is a
conflict-free timetable), examination timetabling, frequency assignment, and
register allocation in compilers (colours = CPU registers, edges = variables
simultaneously live).

![Proper vertex colouring of the cycle C5 with chromatic number 3](img/l10_colouring.png)

**Lower bounds.** If $G$ contains a **clique** of size $k$ (a copy of $K_k$, i.e.
$k$ mutually adjacent vertices), then those $k$ vertices need $k$ distinct colours,
so $\chi(G) \ge k$. Writing $\omega(G)$ for the largest clique size,
$\chi(G)\ge\omega(G)$.

**An upper bound.** $\chi(G) \le \Delta(G)+1$: colour the vertices one at a time in
any order, always choosing the smallest colour not yet used on an already-coloured
neighbour. When a vertex is coloured it has at most $\Delta$ earlier neighbours, so
one of the $\Delta+1$ colours is always free. (This *greedy* procedure and its
analysis as an algorithm are developed in Lecture 11; here we use it only to bound
$\chi$.)

**Basic values.** $\chi(N_n)=1$ (no edges, one colour suffices); $\chi(K_n)=n$
(all vertices mutually adjacent, so $\omega=n$, and $n$ colours clearly suffice).
The next theorem pins down the graphs colourable with two colours.

**Theorem 10.17 (2-colourable = bipartite = no odd cycle).** For any graph $G$ the
following are equivalent: (i) $\chi(G)\le 2$; (ii) $G$ is bipartite; (iii) $G$ has
no cycle of odd length.

*Proof.* **(i) $\Leftrightarrow$ (ii).** A proper $2$-colouring with colours
$\{1,2\}$ is exactly a partition of $V$ into $X=\{$colour $1\}$ and $Y=\{$colour
$2\}$ with no edge inside $X$ or inside $Y$ — which is the definition of bipartite.
(An edgeless graph is bipartite and $1$-colourable, still $\le 2$.)

**(ii) $\Rightarrow$ (iii).** Suppose $G$ is bipartite with parts $X,Y$, and let
$w_0,w_1,\dots,w_k=w_0$ be any cycle. Consecutive vertices are adjacent, hence lie
in opposite parts, so the vertices alternate $X,Y,X,Y,\dots$ along the cycle.
Returning to the start $w_0$ after $k$ steps forces $w_k$ into the same part as
$w_0$, which requires an **even** number of alternations, i.e. $k$ even. So every
cycle has even length; no odd cycle exists.

**(iii) $\Rightarrow$ (ii).** Suppose $G$ has no odd cycle. Colour each component
separately (a disjoint union of bipartite graphs is bipartite), so assume $G$
connected. Fix a root $r$ and let $d(x)$ be the length of a shortest path from $r$
to $x$. Put $X=\{x: d(x)\text{ even}\}$ and $Y=\{x: d(x)\text{ odd}\}$. We claim no
edge joins two vertices of the same part. Suppose $uv$ were such an edge with, say,
$d(u)$ and $d(v)$ of equal parity. Take shortest paths $P_u$ from $r$ to $u$ and
$P_v$ from $r$ to $v$; walking $r\to u$ along $P_u$, across the edge $uv$, and
$v\to r$ along $P_v$ is a closed walk of length $d(u)+1+d(v)$, which is **odd**
because $d(u)+d(v)$ is even. A closed walk of odd length must contain a cycle of
odd length (repeatedly excising even closed sub-walks between repeated vertices
cannot destroy the odd parity, and eventually leaves a cycle) — contradicting the
hypothesis. Hence every edge joins $X$ to $Y$, and $G$ is bipartite.
$\blacksquare$

**Corollary 10.18 (cycles).** An even cycle has $\chi(C_{2k})=2$; an odd cycle has
$\chi(C_{2k+1})=3$.

*Proof.* $C_{2k}$ has no odd cycle (its only cycle has even length $2k$), so by
Theorem 10.17 it is $2$-colourable, and it has an edge so $\chi\ge 2$; thus
$\chi(C_{2k})=2$. $C_{2k+1}$ is itself an odd cycle, so by Theorem 10.17
$\chi>2$, i.e. $\chi\ge 3$; and $3$ colours suffice (colour around the cycle
$1,2,1,2,\dots,1,2,3$, giving the last vertex the spare colour $3$). Thus
$\chi(C_{2k+1})=3$. $\blacksquare$

A **proper edge colouring** assigns a colour to each edge so that **edges sharing a
vertex receive different colours**; the minimum number needed is the **chromatic
index** $\chi'(G)$.

**Proposition 10.19 (edge-colouring lower bound).** $\chi'(G)\ge\Delta(G)$.

*Proof.* The $\Delta(G)$ edges incident with a maximum-degree vertex pairwise share
that vertex, so they must all receive different colours. $\blacksquare$

Remarkably, this lower bound is almost always tight.

**Theorem 10.20 (Vizing, 1964).** Every simple graph satisfies

$$
\chi'(G)\in\{\Delta(G),\ \Delta(G)+1\}.
$$

Vizing's theorem is difficult and we do not prove it; graphs attaining the lower
value $\Delta$ are called *class 1* and those needing $\Delta+1$ are *class 2*.

**Remark (multigraphs).** Vizing's $\Delta+1$ bound is for **simple** graphs. If parallel
edges are allowed, $\chi'$ can exceed $\Delta+1$: Vizing's multigraph bound is
$\chi'\le\Delta+\mu$, where $\mu$ is the largest edge multiplicity. A matching-based
**lower** bound is $\chi'\ge\lceil |E|/\lfloor n/2\rfloor\rceil$, since each colour class
is a matching of at most $\lfloor n/2\rfloor$ edges. (Practical 5 uses both bounds on a
multigraph.)

**Example (vertex colouring of $G$).** The running graph contains the triangle
$a\text{–}b\text{–}c$, a clique of size $3$, so $\chi(G)\ge 3$ by the clique bound.
Three colours suffice: take $a=1,\ b=2,\ c=3$, then $d=2$ (its only coloured
neighbour is $a=1$) and $e=1$ (neighbours $c=3$, $d=2$). Every edge now joins
differently coloured vertices, so $\chi(G)=3$.

**Example (chromatic number vs. index differ).** The $10$-vertex **Petersen graph**
is $3$-regular ($\Delta=3$) with $\chi=3$ and $\chi'=4$. It shows two things at
once: colouring vertices and colouring edges are genuinely different problems, so
$\chi$ and $\chi'$ need not be equal; and a class-$2$ graph exists where Vizing's
upper bound $\Delta+1=4$ is attained. Constructing an optimal colouring (as opposed
to knowing its size) is the algorithmic question of Lecture 11.

**Remark (Four Colour Theorem).** Every *planar* graph is $4$-colourable — the
celebrated Four Colour Theorem, conjectured in 1852 and finally proved by Appel and
Haken in 1976 with substantial computer assistance, the first major theorem so
proved. It says any political map can be coloured with four colours so that
neighbouring regions differ, since the "adjacency graph" of a map is planar.

### The chromatic polynomial

Beyond the *minimum* number of colours, one can count **how many** proper colourings a
graph has. The **chromatic polynomial** $P(G,k)$ is the number of proper vertex
colourings of $G$ using at most $k$ colours; $\chi(G)$ is then the smallest $k$ with
$P(G,k)>0$. It is computed by **deletion–contraction**: for any edge $e=uv$,
$$P(G,k)=P(G-e,\,k)-P(G/e,\,k),$$
where $G-e$ deletes $e$ and $G/e$ contracts it (merges $u,v$) — colourings of $G-e$ that
give $u,v$ the *same* colour are exactly the colourings of $G/e$, so subtracting removes
the improper ones. Base cases: the empty graph $\overline{K_n}$ has $P=k^{n}$; a tree on
$n$ vertices has $P=k(k-1)^{n-1}$; the complete graph has $P(K_n,k)=k(k-1)\cdots(k-n+1)$;
and a cycle has $P(C_n,k)=(k-1)^n+(-1)^n(k-1)$. That $P$ is always a polynomial in $k$ is
itself a theorem (immediate from the recurrence by induction on edges).

### Subgraphs, revisited

Recall (§10.3) that $H$ is a **subgraph** of $G$ if $V(H)\subseteq V(G)$ and
$E(H)\subseteq E(G)$. Two special kinds recur: an **induced** subgraph $G[S]$ keeps a
vertex subset $S$ together with **every** edge of $G$ between them (cliques and
independent sets are induced subgraphs); a **spanning** subgraph keeps **all** vertices
($V(H)=V(G)$) and only some edges (a spanning tree is the key example, Lecture 12).
Monotone parameters respect the containment: deleting edges or vertices cannot raise
$\chi$, $\omega$, or the maximum degree.

## Chapter summary

- A **graph** $G=(V,E)$ pairs vertices with unordered edges; a **digraph** uses
  ordered **arcs**. Simple graphs forbid **loops** and **parallel edges**. Order
  $=|V|$, size $=|E|$.
- **Core terms:** **adjacent** vertices, **incident** vertex–edge pairs, **degree**
  $\deg(v)$ (with in-/out-degree for digraphs), **isolated** vertices, pendants,
  $\Delta$, $\delta$, $r$-regular.
- **Handshaking Lemma** (Thm 10.1): $\sum_v\deg(v)=2|E|$, by double-counting
  incidences. **Corollary 10.2:** the number of odd-degree vertices is even.
  Digraph version (Prop 10.3): $\sum\deg^+=\sum\deg^-=|A|$. **Prop 10.4:** any simple
  graph on $\ge 2$ vertices has two vertices of equal degree.
- **Edge counts** (Thm 10.5): $|E(K_n)|=\binom{n}{2}$, $|E(K_{m,n})|=mn$; a simple
  graph has at most $\binom{n}{2}$ edges, uniquely maximised by $K_n$ (Thm 10.6).
- **Representations:** the symmetric $n\times n$ **adjacency matrix** (row sums =
  degrees) and the $n\times|E|$ **incidence matrix** (column sums $=2$). **Thm 10.7:**
  $(A^k)_{ij}$ counts walks of length $k$ from $v_i$ to $v_j$ (proved by
  induction); the diagonal of $A^2$ gives degrees and
  $\operatorname{trace}(A^3)=6\times(\#\text{triangles})$. **Weighted graphs**
  attach a cost $w(e)$ to each edge.
- **Movement:** **walk** $\supseteq$ **trail** (no repeated edge) $\supseteq$
  **path** (no repeated vertex); closed versions are **circuit** (closed trail)
  and **cycle** (closed path). **Thm 10.8:** a walk from $u$ to $v$ yields a path.
- **Connectivity:** a path joins every pair of vertices; "reachable" is an
  equivalence relation whose classes are the **components** (Prop 10.9). Digraphs
  distinguish **strong** vs **weak** connectivity.
- **Isomorphism:** a bijection preserving adjacency. Prove it by exhibiting the map;
  disprove it via a differing **invariant** (order, size, degree sequence, #
  components, girth, # triangles, bipartiteness). Degree sequence is an invariant
  (Prop 10.10) but not a complete one — $K_{3,3}$ and the prism share it yet differ.
- **Planarity:** drawable without crossings. **Euler's formula** $v-e+f=2$ for
  connected plane graphs (Thm 10.11, induction on edges), giving $e\le 3v-6$
  (Cor 10.12) and, triangle-free, $e\le 2v-4$ (Cor 10.14); hence $K_5$ (Cor 10.13) and
  $K_{3,3}$ (Cor 10.15) are non-planar. **Kuratowski** (Thm 10.16): planar iff no
  subdivision of $K_5$ or $K_{3,3}$.
- **Colouring:** **chromatic number** $\chi(G)$ (vertices) and **chromatic index**
  $\chi'(G)$ (edges). $\omega\le\chi\le\Delta+1$; $\chi(K_n)=n$; $\chi\le 2\iff$
  bipartite $\iff$ no odd cycle (Thm 10.17); $\chi'\ge\Delta$ and, by Vizing,
  $\chi'\in\{\Delta,\Delta+1\}$.

## Exercises

### Warm-up

1. A graph has $10$ vertices, each of degree $3$. How many edges does it have?
   Explain why **no** graph can have exactly $7$ vertices each of degree $3$.

2. Give the general formula and the number for $|E(K_8)|$ and $|E(K_{4,7})|$.

3. Write the adjacency matrix and the incidence matrix of the path
   $a\text{–}b\text{–}c\text{–}d$, and verify that the row sums give the degrees and
   that each incidence-matrix column sums to $2$.

4. Classify each of these walks in the running graph $G$ as walk / trail / path /
   circuit / cycle, and give its length: (i) $b\text{–}a\text{–}c\text{–}b$;
   (ii) $d\text{–}a\text{–}b\text{–}c\text{–}e$; (iii) $a\text{–}c\text{–}a$;
   (iv) $a\text{–}b\text{–}c\text{–}a\text{–}d\text{–}e\text{–}c$.

5. Which of the following can be the degree sequence of a **simple** graph? For
   each, either draw one or explain the obstruction: (i) $(2,2,2)$;
   (ii) $(3,3,2,1)$; (iii) $(1,1,1)$; (iv) $(4,2,2,1,1)$.

6. Compute $\chi$ and $\chi'$ for $C_4$, $C_5$, and $K_4$. Justify each value.

### Standard

7. Prove that in any group of $n\ge 2$ people, at least two people have the same
   number of friends **within the group**. (Model as a simple graph and apply
   Proposition 10.4.)

8. Let $A$ be the adjacency matrix of the running graph $G$ (§10.6). Using $A^2$
   given in the text, state (i) the number of length-$2$ walks from $b$ to $d$ and
   list them; (ii) the number of length-$2$ walks from $c$ to $e$, and explain the
   value; (iii) why the diagonal of $A^2$ reproduces the degree sequence.

9. Decide whether the two graphs below are isomorphic. If they are, give an explicit
   bijection and verify it on edges; if not, name an invariant that differs.
   $G_1$: vertices $\{1,2,3,4,5,6\}$, edges $\{12,23,34,45,56,61\}$.
   $G_2$: vertices $\{1,2,3,4,5,6\}$, edges $\{14,42,25,53,36,61\}$.

10. Exhibit two **connected** simple graphs on $6$ vertices that have the same
    degree sequence but are not isomorphic, and prove they are not isomorphic.

11. Use the bounds $e\le 3v-6$ and (where relevant) $e\le 2v-4$ to decide planarity:
    (i) $K_6$; (ii) $K_{2,3}$; (iii) the Petersen graph ($v=10$, $e=15$, girth $5$).
    For those the bounds cannot settle, say so explicitly.

12. A connected planar graph is drawn so that every face (including the outer one)
    is bounded by exactly $5$ edges, and it has $v=20$ vertices. Find $e$ and $f$.
    (Use $\sum_F\deg F = 2e$ together with Euler's formula.)

13. Show that the graph with vertices $\{1,\dots,6\}$ and edges
    $\{12,23,34,45,56,61,13\}$ is **not** bipartite by exhibiting an odd cycle;
    then find $\chi$ for it.

14. In a directed graph modelling a round-robin tournament among $n$ players (each
    pair plays once, an arc points from winner to loser), prove that
    $\sum_v\deg^+(v)=\binom{n}{2}$, and deduce the average number of wins.

### Challenge

15. Prove that every connected graph on $v$ vertices has at least $v-1$ edges.
    (Hint: induct on $v$, or delete a non-cut edge / contract; relate to trees in
    Lecture 12.)

16. Reprove the triangle-free bound $e\le 2v-4$ for a simple connected planar graph
    with girth $\ge 4$ and $v\ge 3$, and use it to give a self-contained proof that
    $K_{3,3}$ is non-planar. Then explain why the same argument does **not** rule
    out planarity of $K_{2,3}$.

17. (a) Reproduce the proof that $(A^k)_{ij}$ counts walks of length $k$.
    (b) Prove that a simple graph on $n$ vertices is connected **iff** every entry
    of $(I+A)^{\,n-1}$ is strictly positive. (Hint: entry $(i,j)$ positive means
    some walk of length $\le n-1$ joins $v_i,v_j$; use Theorem 10.8 to bound path
    lengths by $n-1$.)

18. Prove that a finite simple graph in which every vertex has degree at least $2$
    contains a cycle. (Hint: consider a longest path and its final vertex — see the
    worked argument at the end of §10.8.)

## Selected answers & hints

**1.** By Handshaking, $2|E|=\sum\deg=10\cdot 3=30$, so $|E|=15$. For $7$ vertices
of degree $3$: that would be $7$ odd-degree vertices, but Corollary 10.2 forces an
**even** number of odd-degree vertices, so it is impossible. (Equivalently
$\sum\deg=21$ is odd, contradicting $2|E|$ even.)

**3.** With order $a,b,c,d$, adjacency matrix rows are
$a\!:\!(0,1,0,0)$, $b\!:\!(1,0,1,0)$, $c\!:\!(0,1,0,1)$, $d\!:\!(0,0,1,0)$; row
sums $1,2,2,1$ are the degrees. Edges $e_1=ab,e_2=bc,e_3=cd$: each column of the
$4\times 3$ incidence matrix has exactly two $1$s.

**4.** (i) closed trail with no repeated interior vertex $\Rightarrow$ **cycle**
(a triangle, $C_3$), length $3$. (ii) no repeated vertex $\Rightarrow$ **path**,
length $4$. (iii) $a\text{–}c\text{–}a$ reuses the edge $ac$, so it is a closed
**walk** but not a trail (hence not a circuit), length $2$. (iv) edges
$ab,bc,ca,ad,de,ec$ are all distinct and it is open ($a$ to $c$), with vertex $a$
and $c$... note $a$ repeats, so it is a **trail** but not a path, length $6$.

**5.** (i) yes — the triangle $C_3$. (ii) sum $=9$ is odd, so **impossible** (no
graph, simple or not). (iii) sum $=3$ odd $\Rightarrow$ **impossible**. (iv) sum
$=10$ even; the degree-$4$ vertex in a simple graph on $5$ vertices must join all
others — realisable, e.g. a vertex joined to all, plus one extra edge; **yes**.

**6.** $C_4$: $\chi=2$ (even cycle, bipartite), $\chi'=2=\Delta$. $C_5$: $\chi=3$
(odd cycle), $\chi'=3=\Delta+1$ (class 2). $K_4$: $\chi=4$ ($\omega=4$),
$\chi'=3=\Delta$ (colour edges as a proper $3$-edge-colouring of $K_4$).

**7.** Vertices $=$ people, edges $=$ mutual friendships; this is a simple graph on
$n\ge 2$ vertices. By Proposition 10.4 two vertices share a degree, i.e. two people
have the same number of friends in the group.

**9.** Isomorphic — both are $6$-cycles. $G_1$ is $1\text{–}2\text{–}3\text{–}4\text{–}5\text{–}6\text{–}1$; $G_2$ is the cycle
$1\text{–}4\text{–}2\text{–}5\text{–}3\text{–}6\text{–}1$. The bijection
$f=(1\!\to\!1,\,2\!\to\!4,\,3\!\to\!2,\,4\!\to\!5,\,5\!\to\!3,\,6\!\to\!6)$ carries
each edge of $G_1$ to an edge of $G_2$; both are $C_6$.

**11.** (i) $K_6$: $v=6,e=15$; $3v-6=12<15$ $\Rightarrow$ **non-planar**.
(ii) $K_{2,3}$: $v=5,e=6$; $3v-6=9\ge 6$ and $2v-4=6\ge 6$ — bounds are satisfied,
so they cannot prove non-planarity, and indeed $K_{2,3}$ **is** planar. (iii)
Petersen: girth $5\Rightarrow$ triangle-free, so $2v-4=16\ge 15$ — the bound is
*satisfied* and cannot rule out planarity; (Petersen is in fact non-planar, but
that requires Kuratowski, not the counting bounds).

**12.** Every face has degree $5$, so $\sum_F\deg F = 5f = 2e\Rightarrow e=\tfrac{5f}{2}$. Euler: $20-e+f=2\Rightarrow e=18+f$. Then
$\tfrac{5f}{2}=18+f\Rightarrow \tfrac{3f}{2}=18\Rightarrow f=12$, and $e=30$.
(Check: $20-30+12=2$. This is the dodecahedron.)

**15.** Induct on $v$. For $v=1$, $0\ge 0$. For $v>1$ connected, some vertex $u$ can
be chosen so that $G-u$ has as few components as possible; more simply, take a
spanning connected subgraph and delete a leaf of a spanning tree (Lecture 12): each
deletion removes one vertex and one edge and preserves connectivity, so
$e(G)\ge e(\text{tree})=v-1$.

**18.** Let $P:x_0\text{–}\cdots\text{–}x_\ell$ be a longest path. Since
$\deg(x_0)\ge 2$, $x_0$ has a neighbour $y\neq x_1$. Maximality forbids $y\notin P$
(else prepend $y$), so $y=x_j$ for some $j\ge 2$, and
$x_0\text{–}x_1\text{–}\cdots\text{–}x_j\text{–}x_0$ is a cycle.

## Further reading

- K. H. Rosen, *Discrete Mathematics and Its Applications* — the graph-theory
  chapters (graphs and graph models, terminology and special graphs, representing
  graphs and isomorphism, connectivity, Euler and Hamilton paths, planar graphs,
  graph colouring) closely parallel this lecture and offer many additional
  worked problems.
- D. B. West, *Introduction to Graph Theory* — a rigorous, proof-centred treatment;
  see its chapters on fundamental concepts and degree, trees and distance,
  planarity (Euler's formula and Kuratowski's theorem), and colouring (including
  Vizing's theorem).
- Historical background: Euler's 1736 solution of the Seven Bridges of Königsberg
  is widely reprinted and discussed in both texts above as the origin of the
  subject.