40.04.01 · combinatorics / graph-theory-core

Graphs, Basic Invariants, and the Foundational Lemmas

shipped3 tiersLean: none

Anchor (Master): Diestel 2017 *Graph Theory* (5th ed., Springer GTM 173) Ch. 1 and the topological-minors / contraction machinery threaded through Ch. 1, 3, 7, 12; Bollobás 1998 *Modern Graph Theory* (Springer GTM 184) Ch. 1; Tutte 1984 *Graph Theory* (Addison-Wesley) Ch. 1-2; the original sources Euler 1736 (Königsberg), Cayley 1857 (counting trees), Kőnig 1936 (the first textbook of graph theory)

Intuition Beginner

A graph is the simplest record of a relationship: a collection of dots, with a line drawn between two dots whenever they are related in some way. The dots are called vertices and the lines are called edges. People at a party with a line for each handshake, cities with a line for each direct flight, web pages with a line for each link — all of these are the same kind of picture once you forget the details and keep only "which pairs are joined." That deliberate forgetting is the whole point. Graph theory studies what survives when you keep only the pattern of connections.

The first thing you can measure about a vertex is how many lines touch it. This count is the vertex's degree. At a party, your degree is how many hands you shook. There is a small miracle hiding here: every handshake involves two hands, so if you add up everyone's personal count, you have counted each handshake exactly twice. The total of all the degrees is therefore always an even number, equal to twice the number of edges. This is the handshake lemma, and it is the first fact that makes graphs feel like arithmetic rather than just drawing.

Once you have dots and lines you can ask how to travel. A walk follows edges from dot to dot; a path is a walk that never repeats a dot; a cycle is a path that loops back to where it began. Two dots are connected if some walk joins them, and the graph breaks into separate islands, called components, of mutually reachable dots. A graph that is all one island with no loops at all is a tree: the leanest possible way to keep everything connected, with not one edge to spare.

Visual Beginner

Picture five dots labelled $1, 2, 3, 4, 5$ . Draw lines $1 - 2$ , $2 - 3$ , $3 - 1$ , $3 - 4$ , and $4 - 5$ . The first three lines form a little triangle on $1, 2, 3$ ; then a line runs out to $4$ , and one more out to $5$ , like a balloon on a string. You can walk from $1$ all the way to $5$ , so the whole picture is a single connected island.

The table beside the drawing records each vertex's degree and checks the handshake count. The triangle makes vertices $1$ and $2$ touch two lines each; vertex $3$ touches three; vertex $4$ touches two; vertex $5$ touches one.

vertex	lines touching it (degree)
1	2
2	2
3	3
4	2
5	1
total	10

The five lines give five edges, and the degrees total $2 + 2 + 3 + 2 + 1 = 10$ , which is exactly twice five. Each line was counted once at each of its two ends.

Worked example Beginner

Take a graph on six vertices and count its edges using only the degrees, without drawing every line. Suppose the six vertices have degrees $4, 3, 3, 2, 2, 2$ . We find the number of edges.

Step 1. Add up all the degrees. The sum is $4 + 3 + 3 + 2 + 2 + 2 = 16$ .

Step 2. Use the handshake fact. The sum of all degrees equals twice the number of edges, because every edge is counted once at each of its two ends. So twice the number of edges is $16$ .

Step 3. Divide by two. The number of edges is $16 \div 2 = 8$ . The graph has exactly eight edges, whatever its detailed shape.

Step 4. Check that the degrees are even possible. The total came out even, which it had to: a list of degrees can describe a real graph only if the degrees add up to an even number. A list like $3, 3, 3$ adds to $9$ , an odd total, so no graph has exactly three vertices each of degree three.

What this tells us: the degrees alone pin down the edge count, and they obey a parity rule that rejects impossible lists. You never had to see the picture. The handshake lemma turned a drawing question into a one-line sum, and that is the flavour of nearly every basic graph invariant — a global quantity read off from local counts.

Check your understanding Beginner

Formal definition Intermediate+

A graph is a pair $G = (V, E)$ where $V$ is a finite set of vertices and $E \subseteq (2 V)$ is a set of edges, each edge an unordered pair ${u, v}$ of distinct vertices ^{[Diestel 2017 §1.1]}. This is the simple graph convention: no loops ${v, v}$ and no repeated edges; multigraphs (allowing parallel edges and loops) are the natural relaxation used for edge counting in Euler's theorem below. Write $n = ∣ V ∣$ for the order and $m = ∣ E ∣$ for the size. Vertices $u, v$ are adjacent if ${u, v} \in E$ , written $u \sim v$ ; a vertex $v$ and an edge $e$ are incident if $v \in e$ . The neighbourhood $N (v) = {u : u \sim v}$ collects the vertices adjacent to $v$ , and the degree $d (v) = ∣ N (v) ∣$ counts them. The minimum and maximum degree are $δ (G) = min_{v} d (v)$ and $Δ (G) = max_{v} d (v)$ , and the average degree is $\overset{ˉ}{d} (G) = \frac{1}{n} \sum_{v \in V} d (v) = 2 m / n$ .

A graph $H = (V^{'}, E^{'})$ is a subgraph of $G$ , written $H \subseteq G$ , if $V^{'} \subseteq V$ and $E^{'} \subseteq E$ . It is an induced subgraph $G [V^{'}]$ if $E^{'} = E \cap (2 V ^{'})$ — every edge of $G$ between two vertices of $V^{'}$ is kept — and a spanning subgraph if $V^{'} = V$ . A walk of length $k$ is a sequence $v_{0} v_{1} \dots v_{k}$ with $v_{i - 1} \sim v_{i}$ for each $i$ ; it is a path if the $v_{i}$ are distinct, and a cycle if $k \geq 3$ , the vertices $v_{0}, \dots, v_{k - 1}$ are distinct, and $v_{k} = v_{0}$ . The girth $g (G)$ is the length of a shortest cycle (infinite if $G$ is acyclic). Vertices $u, v$ lie in the same component if some walk joins them; this is an equivalence relation on $V$ , and $G$ is connected if it has one component. The distance $dist (u, v)$ is the length of a shortest $u$ – $v$ path, and the diameter is $diam (G) = max_{u, v} dist (u, v)$ .

Definition (tree, forest, spanning tree). A forest is an acyclic graph; a tree is a connected forest. A leaf is a vertex of degree $1$ . A spanning tree of a connected $G$ is a spanning subgraph that is a tree.

Definition (bipartite). $G$ is bipartite if $V$ partitions into two parts $A ⊔ B$ with every edge having one end in $A$ and one in $B$ — equivalently, $G$ admits a proper $2$ -colouring.

Definition (contraction, minor, topological minor). Contracting an edge $e = {u, v}$ produces $G / e$ , the graph on $(V ∖ {u, v}) \cup {w_{e}}$ obtained by deleting $u, v$ , adding a new vertex $w_{e}$ adjacent to every former neighbour of $u$ or $v$ , and discarding parallel edges and the loop. $H$ is a minor of $G$ , written $H ≼ G$ , if $H$ arises from a subgraph of $G$ by a sequence of edge contractions; equivalently there are disjoint connected branch sets ${B_{x}}_{x \in V (H)}$ in $G$ with an edge between $B_{x}$ and $B_{y}$ whenever $x \sim y$ in $H$ . $H$ is a topological minor of $G$ if $G$ contains a subdivision of $H$ — a copy of $H$ with edges replaced by internally disjoint paths. Every topological minor is a minor.

Counterexamples to common slips

A subgraph is not the same as an induced subgraph. On the triangle $K_{3}$ , taking the three vertices but only two of the edges is a subgraph; it is not induced, because the induced subgraph on all three vertices must include the third edge. Induced subgraphs are determined by their vertex set; arbitrary subgraphs are not.
A walk may repeat; a path may not. In a triangle $1 - 2 - 3 - 1$ the sequence $121$ is a walk of length $2$ but not a path. Every $u$ – $v$ walk contains a $u$ – $v$ path (delete the loop between repeated vertices), which is why distance is well defined.
Cycles need length at least three. The definition forbids length- $2$ "cycles" $v_{0} v_{1} v_{0}$ ; in a simple graph those are not cycles at all, merely a back-and-forth walk on one edge. This is why bipartite graphs forbid odd cycles rather than all closed walks: a closed walk may have even length by backtracking.
Minimum degree large does not force the whole graph dense. A long path has minimum degree $1$ yet is connected; a disjoint union of triangles has minimum degree $2$ yet diameter is undefined across components. Degree conditions constrain local structure, not connectivity, unless coupled with it.

Key theorem with proof Intermediate+

Theorem (the foundational lemmas: handshake, tree characterisation, and minimum-degree averaging). Let $G = (V, E)$ be a graph with $n$ vertices and $m$ edges.

(a) Handshake lemma. $\sum_{v \in V} d (v) = 2 m$ . Consequently the number of vertices of odd degree is even.

(b) Tree characterisation. The following are equivalent: (i) $G$ is a tree; (ii) $G$ is connected and $m = n - 1$ ; (iii) $G$ is acyclic and $m = n - 1$ ; (iv) any two vertices are joined by a unique path.

(c) Averaging lemma. If $G$ has average degree $\overset{ˉ}{d} \geq d$ , then $G$ has a subgraph $H$ with minimum degree $δ (H) > d /2$ .

(See ^{[Diestel 2017 §1.2-§1.5]}, ^{[Bondy-Murty 2008 Ch. 1-2]}.)

Proof. Part (a). Count incident vertex-edge pairs ${(v, e) : v \in e}$ in two ways. Summing over vertices gives $\sum_{v} d (v)$ , since $v$ lies in exactly $d (v)$ edges. Summing over edges gives $2 m$ , since each edge has exactly two ends. The two counts are equal, so $\sum_{v} d (v) = 2 m$ . Reducing modulo $2$ , the odd-degree vertices each contribute $1$ and the even-degree vertices $0$ , so the number of odd-degree vertices is congruent to $2 m \equiv 0 (mod 2)$ , hence even.

Part (b). We show (i) $\Rightarrow$ (iv) $\Rightarrow$ (ii) $\Rightarrow$ (iii) $\Rightarrow$ (i). Assume (i): $G$ is connected and acyclic. Between any $u, v$ a path exists by connectivity; if two distinct $u$ – $v$ paths existed, following one out and the other back would trace a closed walk containing a cycle, against acyclicity, so the path is unique — this is (iv). Assume (iv): unique paths between all pairs. Connectivity is immediate. For the edge count, root the graph at any vertex $r$ and map each $v \neq = r$ to the first edge on its unique $r$ – $v$ path; this is injective, because that edge's far endpoint $v^{'}$ has its own unique path $r, \dots, v^{'}$ extended to $v$ , so distinct $v$ give distinct last edges by uniqueness, and the map hits every edge exactly once, giving $m = n - 1$ — this is (ii).

Assume (ii): connected with $m = n - 1$ . A connected graph has a spanning tree $T$ , and any spanning tree on $n$ vertices has exactly $n - 1$ edges (build it by adding vertices one at a time, each new vertex contributing one edge). Since $T \subseteq G$ , $T$ already uses all $n - 1$ edges of $G$ , so $G = T$ is acyclic, giving (iii). Assume (iii): acyclic with $m = n - 1$ . Let the components be $C_{1}, \dots, C_{k}$ , each a tree (connected and acyclic), so each $C_{i}$ with $n_{i}$ vertices has $n_{i} - 1$ edges. Then $m = \sum_{i} (n_{i} - 1) = n - k$ , and $m = n - 1$ forces $k = 1$ : $G$ is connected, hence a tree, giving (i).

Part (c). Build a descending sequence of subgraphs $G = G_{0} \supseteq G_{1} \supseteq \dots$ : at each step, if the current $G_{i}$ has a vertex $v$ with $d_{G_{i}} (v) \leq d /2$ , delete $v$ to form $G_{i + 1}$ ; otherwise stop. Track the quantity $Φ (G_{i}) = # E (G_{i}) - \frac{d}{2} # V (G_{i})$ . Deleting a vertex $v$ of degree $\leq d /2$ removes $d_{G_{i}} (v)$ edges and one vertex, so $Φ$ changes by $- d_{G_{i}} (v) + \frac{d}{2} \geq 0$ and never decreases. Initially $Φ (G_{0}) = m - \frac{d}{2} n = \frac{n}{2} (\overset{ˉ}{d} - d) \geq 0$ . The empty graph has $Φ = 0$ , while a single vertex deleted last would pass through a one-vertex graph with $Φ = - d /2 < 0$ , against $Φ \geq 0$ ; so the process cannot delete every vertex and halts at a nonempty $H$ . In $H$ no vertex has degree $\leq d /2$ , so $δ (H) > d /2$ . $□$

Bridge. This theorem builds toward the entire structural and extremal theory of graphs and appears again in every later counting, connectivity, and colouring argument, because all three parts convert a global quantity into a usable local one. The foundational reason the handshake identity, the tree equivalences, and the averaging lemma sit together is that each is a double-counting or a one-edge-at-a-time induction on the same object: the handshake count is exactly the incidence sum that the tree count refines edge-by-edge, and the averaging lemma is that same edge-accounting run as a deletion process. This is exactly the principle that a spanning tree is the minimal connected skeleton whose $n - 1$ edges the handshake lemma then weighs, so the degree sum and the edge count are two readings of one incidence relation. The tree characterisation is dual to the cycle viewpoint: acyclic-plus-counting and connected-plus-counting are the two ways an $(n - 1)$ -edge graph can be a tree, and putting these together gives the spanning-tree existence that every connectivity and matroid argument downstream assumes. The averaging lemma is the bridge from average to guaranteed local density, the first move in extremal graph theory, where a global edge bound must be turned into a dense substructure before any forbidden configuration can be located.

Exercises Intermediate+

Exercise 5 (medium, short-answer).

Show that a graph is bipartite if and only if it has no cycle of odd length.

Hint

For the forward direction, colours alternate along any walk. For the reverse, in each component fix a root and colour each vertex by the parity of its distance from the root.

Answer

( $\Rightarrow$ ) Suppose $G$ is bipartite with parts $A, B$ . Along any walk the part alternates $A, B, A, \dots$ , so a closed walk returns to its start only after an even number of steps; in particular every cycle has even length, so no odd cycle exists. ( $\Leftarrow$ ) Suppose $G$ has no odd cycle. Work component by component; fix a root $r$ and colour each vertex $v$ by the parity of $dist (r, v)$ , putting even-distance vertices in $A$ and odd in $B$ . If some edge ${u, v}$ had both ends the same colour, then $dist (r, u)$ and $dist (r, v)$ have equal parity; concatenating a shortest $r$ – $u$ path, the edge $uv$ , and a shortest $v$ – $r$ path gives a closed walk of odd length, which contains an odd cycle, a contradiction. So every edge joins the two colour classes and $G$ is bipartite. Rubric: full credit for both directions, including the parity-of-distance colouring and the odd-closed-walk-contains-odd-cycle step.

Exercise 6 (medium, symbolic).

Let $A$ be the adjacency matrix of a graph $G$ , with $A_{uv} = 1$ iff $u \sim v$ . Express the number of walks of length $k$ from $u$ to $v$ in terms of $A$ , and deduce a formula for the number of closed walks of length $k$ .

Hint

Induct on $k$ using $(A^{k})_{uv} = \sum_{w} (A^{k - 1})_{u w} A_{w v}$ .

Answer

The number of $u$ – $v$ walks of length $k$ is $(A^{k})_{uv}$ . By induction: for $k = 1$ , $(A)_{uv} = A_{uv}$ counts the length- $1$ walks (edges). For the step, a length- $k$ walk $u \to \dots \to w \to v$ is a length- $(k - 1)$ walk $u \to \dots \to w$ followed by an edge $w v$ , so the count is $\sum_{w} (A^{k - 1})_{u w} A_{w v} = (A^{k})_{uv}$ . The number of closed walks of length $k$ is the sum over starting vertices of $(A^{k})_{v v}$ , namely $tr (A^{k}) = \sum_{i} λ_{i}^{k}$ where $λ_{i}$ are the eigenvalues of $A$ . Rubric: full credit for $(A^{k})_{uv}$ , the inductive step, and $tr (A^{k})$ for closed walks.

Exercise 7 (hard, short-answer).

Prove that a connected graph $G$ has a closed walk traversing every edge exactly once (a closed Euler tour) if and only if every vertex has even degree.

Hint

For necessity, count how an Euler tour enters and leaves each vertex. For sufficiency, take a maximal trail and argue it must close and exhaust the edges, splicing in extra closed trails where edges remain.

Answer

( $\Rightarrow$ ) Suppose a closed Euler tour exists. Each time the tour passes through a vertex $v$ it uses one edge to arrive and one to leave, pairing the edges at $v$ ; the closing of the tour pairs the very first departure with the very last arrival. Every edge at $v$ is used exactly once and lies in exactly one such pair, so $d (v)$ is even. ( $\Leftarrow$ ) Suppose every degree is even and $G$ is connected with at least one edge. Take a trail (a walk with no repeated edge) of maximum length, say from $a$ to $b$ . If $b \neq = a$ , the trail has used an odd number of edges at $b$ (one for each arrival-departure pair plus the final arrival), leaving an unused edge at $b$ by evenness of $d (b)$ , so the trail could be extended — contradiction. Hence the maximal trail is closed, $a = b$ . If it omits some edge, then by connectivity some omitted edge meets a vertex $w$ on the closed trail; starting a fresh maximal trail at $w$ in the graph of unused edges (still all even degrees) yields another closed trail at $w$ , which splices into the first at $w$ to form a longer closed trail — contradicting maximality. So the maximal closed trail uses every edge: it is an Euler tour. Rubric: full credit for the parity necessity and the maximal-trail splicing sufficiency.

Exercise 8 (hard, short-answer).

Prove that a graph $G$ with average degree at least $2 k$ (where $k \geq 1$ is an integer) contains a cycle of length at least $k + 1$ . Use the averaging lemma.

Hint

First extract a subgraph $H$ with $δ (H) > k$ , hence $δ (H) \geq k + 1$ . Then take a longest path in $H$ and look at the neighbours of its endpoint.

Answer

By the averaging lemma with $d = 2 k$ , $G$ has a subgraph $H$ with $δ (H) > 2 k /2 = k$ , so $δ (H) \geq k + 1$ . Let $P = v_{0} v_{1} \dots v_{ℓ}$ be a longest path in $H$ . All neighbours of $v_{0}$ lie on $P$ (otherwise $P$ extends), and $v_{0}$ has at least $k + 1$ neighbours, all among $v_{1}, \dots, v_{ℓ}$ . Let $v_{j}$ be the neighbour of $v_{0}$ with the largest index $j$ . Since $v_{0}$ has $\geq k + 1$ neighbours among $v_{1}, \dots, v_{j}$ , we have $j \geq k + 1$ . The edge $v_{0} v_{j}$ together with the path segment $v_{0} v_{1} \dots v_{j}$ forms a cycle of length $j + 1 \geq k + 2 \geq k + 1$ . (Even the cruder bound, using only that $v_{0}$ has a neighbour at index $\geq k + 1$ , gives a cycle of length $\geq k + 2$ .) Rubric: full credit for the averaging extraction, the longest-path endpoint argument, and the index bound producing a cycle of length $\geq k + 1$ .

Advanced results Master

Theorem (Cayley's formula). The number of labelled trees on the vertex set ${1, \dots, n}$ is $n^{n - 2}$ . (Cayley ^{[Cayley 1889]}; Diestel ^{[Diestel 2017 §1.2]}.) The Prüfer correspondence is a bijection between labelled trees on $n$ vertices and sequences in ${1, \dots, n}^{n - 2}$ : repeatedly remove the leaf of smallest label and record its unique neighbour, producing a length- $(n - 2)$ sequence; the construction reverses uniquely because the multiplicity of a label in the Prüfer sequence is one less than the degree of that vertex, which determines the leaf-removal order. The matrix-tree theorem of Kirchhoff gives the same count for arbitrary $G$ : the number of spanning trees equals any cofactor of the Laplacian $L = D - A$ , where $D$ is the degree diagonal and $A$ the adjacency matrix, and for $K_{n}$ the nonzero Laplacian eigenvalues are all $n$ , giving $\frac{1}{n} n^{n - 1} = n^{n - 2}$ .

Theorem (high girth forces many vertices: the Moore bound). A graph with minimum degree $δ$ and girth $g$ has at least $n_{0} (δ, g)$ vertices, where for odd $g = 2 r + 1$ , $$ n_0 = 1 + \delta \sum_{i=0}^{r-1} (\delta - 1)^i, $$ and for even $g = 2 r$ a comparable bound holds. (Diestel ^{[Diestel 2017 §1.3, §1.7]}.) The proof is a breadth-first count: from any vertex, the girth condition forces the first $r$ neighbourhood shells to branch without collision, so the ball of radius $r$ has the stated size. The bound makes precise the Beginner slogan that high girth forces many vertices: locally tree-like graphs of fixed degree cannot be small, and the extremal Moore graphs meeting the bound are rare (the Petersen graph for $δ = 3$ , $g = 5$ ; the Hoffman-Singleton graph for $δ = 7$ , $g = 5$ ; almost no others, by the Hoffman-Singleton eigenvalue argument).

Theorem (the minor and topological-minor orders; Kuratowski-Wagner). A graph is planar iff it contains neither $K_{5}$ nor $K_{3, 3}$ as a minor, iff it contains neither as a topological minor. (Diestel ^{[Diestel 2017 §1.7]}.) For graphs of maximum degree $\leq 3$ the minor and topological-minor relations coincide, since a branch set of a degree- $\leq 3$ model can be realised by a subdivision. The minor relation is a well-quasi-order on the class of all finite graphs (Robertson-Seymour), so every minor-closed graph property has a finite set of forbidden minors — the structural endpoint of the contraction language introduced in the formal definition.

Theorem (degree sequences: Erdős-Gallai). A non-increasing sequence $d_{1} \geq \dots \geq d_{n}$ of non-negative integers is the degree sequence of some graph iff $\sum_{i} d_{i}$ is even and for every $k$ , $$ \sum_{i=1}^{k} d_i \leq k(k-1) + \sum_{i=k+1}^{n} \min(d_i, k). $$ (Diestel ^{[Diestel 2017 §1.2]}.) The parity condition is the handshake lemma; the family of inequalities encodes that the $k$ largest-degree vertices cannot demand more edges than the rest of the graph can supply. The Havel-Hakimi algorithm gives a constructive equivalent: a sequence is graphical iff deleting the largest degree $d_{1}$ and subtracting $1$ from the next $d_{1}$ entries leaves a graphical sequence.

Synthesis. These results are one foundation seen at increasing depth, and putting these together the whole first chapter becomes the study of two dual skeletons of a graph — its spanning trees and its cycle space — weighed by the single incidence relation the handshake lemma counts. The central insight is that a tree is the minimal connected structure with $n - 1$ edges, so Cayley's $n^{n - 2}$ , the matrix-tree determinant, and the spanning-tree existence used everywhere are three readings of the same minimal skeleton; this is exactly the principle that the handshake double-count refines into the tree edge-count and then into the Laplacian cofactor. The averaging lemma is dual to the Moore bound: average degree pushed up guarantees a dense minimum-degree core, while girth pushed up forces that same degree to spread over many vertices, so density and locally-tree-like sparsity are the two regimes the foundational lemmas separate. The bridge onward is the minor order, which generalises subgraph containment to the contraction-stable relation under which planarity, and ultimately every minor-closed property, has a finite forbidden-minor description — the foundational reason structural graph theory organises itself around minors rather than subgraphs. The degree-sequence theorem closes the loop, characterising exactly which local degree data the handshake parity permits, so the invariants this unit defines are not merely measured but realised, the realisation question that every later extremal and structural theorem refines.

Full proof set Master

Proposition 1 (handshake lemma). For any graph, $\sum_{v} d (v) = 2∣ E ∣$ , and the number of odd-degree vertices is even.

Proof. Consider the incidence set $I = {(v, e) \in V \times E : v \in e}$ . Counting $I$ by its first coordinate, each $v$ appears in exactly $d (v)$ pairs, so $∣ I ∣ = \sum_{v} d (v)$ . Counting by the second coordinate, each edge $e = {u, w}$ contributes exactly the two pairs $(u, e), (w, e)$ , so $∣ I ∣ = 2∣ E ∣$ . Equating, $\sum_{v} d (v) = 2∣ E ∣$ . Modulo $2$ , $\sum_{v} d (v) \equiv 0$ , and the even-degree terms vanish modulo $2$ , so the count of odd terms is $\equiv 0 (mod 2)$ , hence even. $□$

Proposition 2 (every connected graph has a spanning tree, with exactly $n - 1$ edges). A connected graph $G$ on $n$ vertices contains a spanning tree, and every spanning tree has $n - 1$ edges.

Proof. Among all connected spanning subgraphs of $G$ pick one, $T$ , with the fewest edges. If $T$ contained a cycle, deleting any cycle edge would keep $T$ connected (a cycle edge lies on a cycle, so its endpoints remain joined by the rest of the cycle) with fewer edges, contradicting minimality. So $T$ is acyclic and connected: a spanning tree. For the edge count, order the vertices $v_{1}, \dots, v_{n}$ so that each $v_{i}$ ( $i \geq 2$ ) is adjacent in $T$ to some earlier vertex — possible by connectivity, growing a connected set one vertex at a time. Each $v_{i}$ for $i \geq 2$ contributes exactly one new edge to $T$ (the edge to its earlier neighbour; a second edge to an earlier vertex would close a cycle), and $v_{1}$ contributes none, so $T$ has $n - 1$ edges. $□$

Proposition 3 (tree characterisation, full equivalence). For a graph $G$ on $n$ vertices, the four conditions (i) tree, (ii) connected with $n - 1$ edges, (iii) acyclic with $n - 1$ edges, (iv) unique paths, are equivalent.

Proof. (i) $\Rightarrow$ (iv): a tree is connected, so paths exist; two distinct $u$ – $v$ paths would produce, by symmetric difference, a nonempty even subgraph with all degrees even, which contains a cycle, against acyclicity. (iv) $\Rightarrow$ (i): unique paths give connectivity; a cycle would give two distinct paths between any two of its vertices, so $G$ is acyclic — a tree. (i) $\Rightarrow$ (ii): Proposition 2 gives $n - 1$ edges and connectivity is part of (i). (ii) $\Rightarrow$ (iii): a connected graph on $n$ vertices with $n - 1$ edges equals its spanning tree (which already has $n - 1$ edges by Proposition 2), so it is acyclic. (iii) $\Rightarrow$ (i): with components $C_{1}, \dots, C_{k}$ of orders $n_{i}$ , each component is connected and acyclic, hence a tree with $n_{i} - 1$ edges, so $∣ E ∣ = \sum (n_{i} - 1) = n - k$ ; the hypothesis $∣ E ∣ = n - 1$ forces $k = 1$ , so $G$ is connected, hence a tree. The cycle of implications closes, so all four are equivalent. $□$

Proposition 4 (averaging lemma). If $G$ has average degree $\geq d > 0$ , it has a nonempty subgraph $H$ with $δ (H) > d /2$ .

Proof. Run the deletion process: while the current subgraph $G^{'}$ has a vertex of degree $\leq d /2$ , delete one such vertex. Track $Φ (G^{'}) = ∣ E (G^{'}) ∣ - \frac{d}{2} ∣ V (G^{'}) ∣$ . Initially $Φ (G) = m - \frac{d}{2} n = \frac{n}{2} (\overset{ˉ}{d} - d) \geq 0$ . Deleting a vertex $v$ with $d_{G^{'}} (v) \leq d /2$ removes $d_{G^{'}} (v)$ edges and one vertex, changing $Φ$ by $- d_{G^{'}} (v) + \frac{d}{2} \geq 0$ ; thus $Φ$ never decreases. The empty graph has $Φ = 0$ . If the process deleted all vertices, then since $Φ$ is nondecreasing and ends at $0$ , it must have started at $Φ (G) \leq 0$ , forcing $\overset{ˉ}{d} = d$ and every deletion tight; but the last deletion removes a vertex of degree $0$ from a one-vertex graph with $Φ = - d /2 < 0$ , contradicting $Φ \geq 0$ throughout. Hence the process halts at a nonempty $H$ in which no vertex has degree $\leq d /2$ , i.e. $δ (H) > d /2$ . $□$

Proposition 5 (Euler's theorem). A connected graph (or multigraph) with at least one edge has a closed Euler tour iff every vertex has even degree.

Proof. Necessity: a closed Euler tour visits each vertex pairing an entering edge with a leaving edge, and the closing identifies the first and last; every incident edge appears once and lies in one pair, so each degree is even. Sufficiency: assume all degrees even. Take a trail $W$ of maximum length. Its terminus $b$ has used, in $W$ , an even number of edges if $b$ is an interior repeat and otherwise pairs all but possibly the final edge; precisely, if $W$ ended at $b \neq = a$ , the edges of $W$ at $b$ number one more than a multiple of two on the arrival side, leaving an unused edge at $b$ by evenness, so $W$ extends — contradiction. Hence $W$ is closed. If $W$ omits an edge, connectivity gives a vertex $w$ on $W$ incident to an unused edge; a maximal trail in the unused-edge graph from $w$ (all degrees still even there) is closed at $w$ and splices into $W$ , lengthening it — contradiction. So $W$ traverses every edge once: a closed Euler tour. $□$

Proposition 6 (Cayley's formula via Prüfer). There are exactly $n^{n - 2}$ labelled trees on ${1, \dots, n}$ for $n \geq 2$ .

Proof. Define the Prüfer map from trees to sequences in ${1, \dots, n}^{n - 2}$ : given a tree, repeatedly delete the leaf of smallest label and append the label of its unique neighbour, stopping when two vertices remain; this yields a sequence of length $n - 2$ . The map is a bijection. Injectivity and surjectivity follow from a single observation: in the sequence produced, a vertex $v$ appears exactly $d (v) - 1$ times, because $v$ is recorded once for each neighbour deleted before $v$ itself, and $v$ is deleted (ceasing to be recorded) after its degree drops to $1$ . Given any sequence $s \in {1, \dots, n}^{n - 2}$ , the degrees are forced by $d (v) = 1 + (count of v in s)$ , and the tree is reconstructed uniquely: at each step the smallest-labelled vertex not in the remaining sequence and not yet used is a current leaf, joined to the first sequence entry, which is then removed. This inverse is well defined and single-valued, so the Prüfer map is a bijection and the number of trees is $∣ {1, \dots, n}^{n - 2} ∣ = n^{n - 2}$ . $□$

Connections Master

Data structures: arrays, trees, and graphs 25.02.01. The structural graph defined here is the mathematical object behind the computer-science data structure: adjacency lists and adjacency matrices are concrete encodings of the edge set $E \subseteq (2 V)$ , breadth-first and depth-first search compute the components and distances defined in the formal section, and the spanning tree of Proposition 2 is exactly what a traversal produces. This unit owns the invariants — degree, girth, connectivity, the tree characterisation — while the algorithmic unit owns their computation; the handshake lemma is the reason an adjacency-list traversal costs $O (∣ V ∣ + ∣ E ∣)$ rather than $O (∣ V ∣^{2})$ .
Eigenvalue and eigenvector 01.01.08. The adjacency and Laplacian matrices turn the combinatorial invariants of this unit into spectral ones: the number of closed walks of length $k$ is $tr (A^{k}) = \sum_{i} λ_{i}^{k}$ (Exercise 6), the multiplicity of the Laplacian eigenvalue $0$ equals the number of components, and the matrix-tree theorem computes spanning-tree counts from Laplacian cofactors. The bipartite criterion of the Key theorem is the spectral statement that $A$ 's spectrum is symmetric about $0$ , so the foundational lemmas here are the combinatorial source of all of spectral graph theory.
Extremal graph theory and the Turán-type bounds 40.05.01. The averaging lemma is the first move of extremal graph theory: it converts a global average-degree hypothesis into a dense subgraph of large minimum degree, the standard preprocessing before forbidding a subgraph forces structure. Exercise 8's cycle-length bound and the Moore bound of the Advanced section are the two faces — density and girth — that the extremal chapter develops into Turán's theorem and the Kővári-Sós-Turán bound, all resting on the degree and counting invariants established here.

Historical & philosophical context Master

Graph theory begins with Leonhard Euler's 1736 solution of the Seven Bridges of Königsberg, Solutio problematis ad geometriam situs pertinentis (Commentarii Academiae Scientiarum Petropolitanae 8) ^{[Euler 1736]}, in which Euler abstracted the city's landmasses to points and its bridges to connections and proved that a closed walk crossing every bridge exactly once requires every landmass to meet an even number of bridges. This is the even-degree criterion of Proposition 5, and the abstraction — keep the incidences, discard the geometry — is the founding move of the subject Euler called the geometry of position. The counting of trees was carried out by Arthur Cayley, whose 1889 note A theorem on trees (Quarterly Journal of Pure and Applied Mathematics 23) ^{[Cayley 1889]} established the $n^{n - 2}$ formula in the course of counting saturated hydrocarbons, tying the combinatorics of trees to chemical isomer enumeration.

The systematic theory consolidated in the early twentieth century. Dénes Kőnig's 1936 Theorie der endlichen und unendlichen Graphen was the first textbook devoted to graphs and fixed much of the modern vocabulary of degrees, paths, cycles, and bipartiteness. Gustav Kirchhoff's 1847 work on electrical networks had already produced the matrix-tree theorem as a tool for counting independent current loops, and Heinz Prüfer's 1918 bijective proof of Cayley's formula supplied the encoding used in Proposition 6. The contraction and minor language, latent in Kazimierz Kuratowski's 1930 and Klaus Wagner's 1937 planarity criteria, became the organising relation of structural graph theory through the Robertson-Seymour graph-minors project of 1983-2004, which proved that finite graphs are well-quasi-ordered under the minor relation. The textbook synthesis followed in Reinhard Diestel's Graph Theory ^{[Diestel 2017]}, which organises the first chapter around exactly the degree, connectivity, tree, bipartite, Euler, and minor material of this unit.

Bibliography Master

@book{Diestel2017,
  author    = {Diestel, Reinhard},
  title     = {Graph Theory},
  edition   = {5th},
  series    = {Graduate Texts in Mathematics},
  volume    = {173},
  publisher = {Springer},
  year      = {2017}
}

@book{BondyMurty2008,
  author    = {Bondy, J. A. and Murty, U. S. R.},
  title     = {Graph Theory},
  series    = {Graduate Texts in Mathematics},
  volume    = {244},
  publisher = {Springer},
  year      = {2008}
}

@book{Bollobas1998,
  author    = {Bollob\'as, B\'ela},
  title     = {Modern Graph Theory},
  series    = {Graduate Texts in Mathematics},
  volume    = {184},
  publisher = {Springer},
  year      = {1998}
}

@article{Euler1736,
  author  = {Euler, Leonhard},
  title   = {Solutio problematis ad geometriam situs pertinentis},
  journal = {Commentarii Academiae Scientiarum Petropolitanae},
  volume  = {8},
  year    = {1736},
  pages   = {128--140}
}

@article{Cayley1889,
  author  = {Cayley, Arthur},
  title   = {A theorem on trees},
  journal = {Quarterly Journal of Pure and Applied Mathematics},
  volume  = {23},
  year    = {1889},
  pages   = {376--378}
}

@book{Konig1936,
  author    = {K\H{o}nig, D\'enes},
  title     = {Theorie der endlichen und unendlichen Graphen},
  publisher = {Akademische Verlagsgesellschaft},
  year      = {1936}
}

@article{RobertsonSeymour2004,
  author  = {Robertson, Neil and Seymour, Paul D.},
  title   = {Graph Minors. XX. Wagner's conjecture},
  journal = {Journal of Combinatorial Theory, Series B},
  volume  = {92},
  year    = {2004},
  pages   = {325--357}
}

Prerequisites

none — this is a leaf unit

Tier anchors

beginner: Diestel 2017 *Graph Theory* (5th ed., Springer GTM 173) §1.1-§1.5 (graphs, degree, paths, cycles, trees) read for the pictures and small examples; West 2001 *Introduction to Graph Theory* (2nd ed., Prentice Hall) Ch. 1 for the hand-drawn dots-and-lines vocabulary and the handshake count; 3Blue1Brown's combinatorics and Euler-characteristic essays for the walk-on-a-graph intuition
intermediate: Diestel 2017 *Graph Theory* (5th ed., Springer GTM 173) Ch. 1 (the degree formula, connectivity and components, trees and their characterisations, bipartite graphs and the odd-cycle criterion, the minimum-degree averaging lemma, Euler tours, contraction and minors); Bondy-Murty 2008 *Graph Theory* (Springer GTM 244) Ch. 1-3
master: Diestel 2017 *Graph Theory* (5th ed., Springer GTM 173) Ch. 1 and the topological-minors / contraction machinery threaded through Ch. 1, 3, 7, 12; Bollobás 1998 *Modern Graph Theory* (Springer GTM 184) Ch. 1; Tutte 1984 *Graph Theory* (Addison-Wesley) Ch. 1-2; the original sources Euler 1736 (Königsberg), Cayley 1857 (counting trees), Kőnig 1936 (the first textbook of graph theory)

References

Diestel 2017 — Graph Theory (5th edition) · Springer Graduate Texts in Mathematics 173, 2017, Ch. 1 (§1.1 graphs; §1.2 the degree of a vertex and the handshake formula; §1.3 paths and cycles; §1.4 connectivity and components; §1.5 trees and forests; §1.6 bipartite graphs; §1.7 contraction and minors; §1.8 Euler tours)
Bondy, Murty 2008 — Graph Theory · Springer Graduate Texts in Mathematics 244, 2008, Ch. 1-3 (graphs and subgraphs, trees, connectivity)
Bollobás 1998 — Modern Graph Theory · Springer Graduate Texts in Mathematics 184, 1998, Ch. 1 (fundamentals: degree sequences, paths, cycles, trees, Euler circuits)
Euler 1736 — Solutio problematis ad geometriam situs pertinentis · Commentarii Academiae Scientiarum Petropolitanae 8 (1736) 128-140; the Seven Bridges of Königsberg and the even-degree criterion for an Euler tour
Cayley 1889 — A theorem on trees · Quarterly Journal of Pure and Applied Mathematics 23 (1889) 376-378; the count n^{n-2} of labelled trees on n vertices

Estimated time

beginner: 18m
intermediate: 46m
master: 84m