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\}.$$

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?

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.

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.

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

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.

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

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

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

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:

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.

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

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

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