Formula & theorem reference

Each edge e = \{u, v\} of G has exactly two endpoints, u and v (a loop at v is the case u = v, still contributing two to that one vertex's degree count, which is exactly why a loop is defined to add 2 to \deg(v) rather than 1). Build the sum \sum_{v\in V}\deg(v) by counting, for every edge, how many times that edge gets counted across the whole sum.

Fix one edge e=\{u,v\}. It is counted once when computing \deg(u) (since e is incident to u) and once more when computing \deg(v) (since e is also incident to v), and it is never counted in any other vertex's degree, since e touches no vertex besides u and v. So every edge contributes exactly 2 to the total \sum_{v\in V}\deg(v), and there are |E| edges, giving \sum_{v \in V} \deg(v) = \sum_{e \in E} 2 = 2|E|.

The odd-degree count is even. Split V into V_{\text{even}} (even degree) and V_{\text{odd}} (odd degree). Then \sum_{v \in V_{\text{even}}} \deg(v) + \sum_{v \in V_{\text{odd}}} \deg(v) = 2|E|, an even number. The first sum is a sum of even numbers, so it's even. Subtracting an even number from an even number leaves an even number, so \sum_{v \in V_{\text{odd}}} \deg(v) is even too. A sum of odd numbers is even only when there is an even count of them (an odd count of odd numbers always sums to something odd), so |V_{\text{odd}}| itself must be even.

Sanity check: a triangle (3 vertices, each of degree 2) has degree sum 2+2+2=6, and 2|E| = 2(3) = 6 -- matches, and 0 vertices have odd degree, which is indeed even.

Necessity. Suppose a matching M saturates L, and let S \subseteq L be any subset. Each vertex of S is matched by M to its own vertex of R, and these matched partners are distinct because no two edges of a matching share an endpoint. Every matched partner of a vertex in S is, in particular, a neighbor of that vertex, so all |S| of them lie in N(S). Hence |N(S)| \ge |S|. Equivalently: if some set S has |N(S)| < |S|, the |S| vertices of S would need distinct partners drawn from fewer than |S| available neighbors, which is impossible — the deficiency |S| - |N(S)| counts vertices of S that must go unmatched.

Sufficiency (sketch). Suppose |N(S)| \ge |S| for every S \subseteq L, and let M be a matching of maximum size. If M did not saturate L, pick an unmatched vertex u \in L and consider all vertices reachable from u by alternating paths (paths whose edges alternate between non-matching and matching edges). Let A \subseteq L and B \subseteq R be the reachable vertices on each side. A standard argument shows every vertex of B is matched (otherwise an augmenting path would let us enlarge M, contradicting maximality) and that B = N(A) with each vertex of A \setminus \{u\} matched into B. Counting then gives |N(A)| = |B| = |A| - 1 < |A|, violating Hall's condition. So M saturates L. The full details of the reachability argument are the standard augmenting-path proof of the theorem.

Induct on n. A tree with n = 1 vertex has no edges at all, and n - 1 = 0, so the base case holds.

Assume every tree on k vertices has exactly k - 1 edges, for some k \geq 1. Let T be a tree on k + 1 vertices. Every tree with more than one vertex has at least one leaf (a vertex of degree 1) — following any path outward without repeating a vertex must eventually stop somewhere, since T is finite and acyclic, and it can only stop at a vertex with no unused edge left, degree 1. Remove that leaf v and its single incident edge. What remains is still connected (no other vertex's connections ran through v, since v had only one edge) and still acyclic (deleting a vertex can't create a cycle), so it is a tree on k vertices. By the inductive hypothesis it has k - 1 edges. Adding v's one edge back gives T exactly (k - 1) + 1 = k edges, which is (k+1) - 1, as required.

By induction, every tree on n vertices has n - 1 edges for all n \geq 1.

We sketch the Prüfer correspondence, a bijection between labeled trees on the vertex set \{1, \ldots, n\} and sequences of length n-2 whose entries come from \{1, \ldots, n\}. Since there are n^{n-2} such sequences, the bijection proves the count.

Tree to sequence. Given a tree T on \{1, \ldots, n\}, repeat the following step n-2 times: find the leaf with the smallest label, write down the label of its unique neighbor, and delete the leaf. The n-2 recorded neighbor labels, in order, form the Prüfer sequence of T. The process is deterministic, so each tree yields exactly one sequence.

Sequence to tree. Given a sequence (a_1, \ldots, a_{n-2}), the degree of each vertex v in the corresponding tree must be one plus the number of times v appears in the sequence: every non-leaf vertex is recorded once for each of its leaf-neighbors deleted while it remains, and once more when it is itself deleted or survives at the end. Rebuild the tree by reversing the deletions: at step i, join a_i to the smallest-labeled vertex that is not among a_i, a_{i+1}, \ldots, a_{n-2} and has not yet been used, then mark that vertex used. After n-2 joins, exactly two vertices remain unused; join them to each other. Each step is forced, so each sequence yields exactly one tree, and rebuilding the sequence's tree recovers the original sequence.

The two maps are mutually inverse, giving a bijection. Hence the number of labeled trees on n vertices equals the number of sequences of length n-2 over an alphabet of size n, which is n^{n-2}. Small cases confirm it: n = 3 gives 3^1 = 3 trees (the three paths on three labeled vertices), and n = 4 gives 4^2 = 16.

Induct on n. A tree with n = 1 vertex has no edges at all, and n - 1 = 0, so the base case holds.

Assume every tree on k vertices has exactly k - 1 edges, for some k \geq 1. Let T be a tree on k + 1 vertices. Every tree with more than one vertex has at least one leaf (a vertex of degree 1) — following any path outward without repeating a vertex must eventually stop somewhere, since T is finite and acyclic, and it can only stop at a vertex with no unused edge left, degree 1. Remove that leaf v and its single incident edge. What remains is still connected (no other vertex's connections ran through v, since v had only one edge) and still acyclic (deleting a vertex can't create a cycle), so it is a tree on k vertices. By the inductive hypothesis it has k - 1 edges. Adding v's one edge back gives T exactly (k - 1) + 1 = k edges, which is (k+1) - 1, as required.

By induction, every tree on n vertices has n - 1 edges for all n \geq 1.

Count nodes level by level, where the root sits at level 0. Level 0 can hold at most 1 = 2^0 node. Every node on a level has at most two children, so the maximum count at least doubles from one level to the next: level 1 holds at most 2 = 2^1 nodes, level 2 at most 4 = 2^2, and in general level i holds at most 2^i nodes.

A tree of height h has levels 0 through h, so its total node count is at most \sum_{i=0}^{h} 2^i = 2^{h+1} - 1, the standard geometric sum. Equality holds exactly when every level attains its own maximum, i.e. every level is completely filled — the definition of a perfect binary tree.

We sketch the Prüfer correspondence, a bijection between labeled trees on the vertex set \{1, \ldots, n\} and sequences of length n-2 whose entries come from \{1, \ldots, n\}. Since there are n^{n-2} such sequences, the bijection proves the count.

Tree to sequence. Given a tree T on \{1, \ldots, n\}, repeat the following step n-2 times: find the leaf with the smallest label, write down the label of its unique neighbor, and delete the leaf. The n-2 recorded neighbor labels, in order, form the Prüfer sequence of T. The process is deterministic, so each tree yields exactly one sequence.

Sequence to tree. Given a sequence (a_1, \ldots, a_{n-2}), the degree of each vertex v in the corresponding tree must be one plus the number of times v appears in the sequence: every non-leaf vertex is recorded once for each of its leaf-neighbors deleted while it remains, and once more when it is itself deleted or survives at the end. Rebuild the tree by reversing the deletions: at step i, join a_i to the smallest-labeled vertex that is not among a_i, a_{i+1}, \ldots, a_{n-2} and has not yet been used, then mark that vertex used. After n-2 joins, exactly two vertices remain unused; join them to each other. Each step is forced, so each sequence yields exactly one tree, and rebuilding the sequence's tree recovers the original sequence.

The two maps are mutually inverse, giving a bijection. Hence the number of labeled trees on n vertices equals the number of sequences of length n-2 over an alphabet of size n, which is n^{n-2}. Small cases confirm it: n = 3 gives 3^1 = 3 trees (the three paths on three labeled vertices), and n = 4 gives 4^2 = 16.

A full proof needs linear-algebra machinery beyond this course, so we state the structure honestly and verify a case rather than pretend to derive it. The standard argument writes L = M M^{\mathsf T}, where M is the incidence matrix of an arbitrary orientation of G, and applies the Cauchy-Binet formula to expand \det(L_{(i)}) as a sum of squared determinants of (n-1) \times (n-1) submatrices of M, one for each choice of n-1 edges. Each such determinant is \pm 1 when the chosen edges form a spanning tree and 0 when they contain a cycle, so the sum counts spanning trees exactly.

Verification on K_3: each vertex has degree 2, so L = \begin{pmatrix} 2 & -1 & -1 \\ -1 & 2 & -1 \\ -1 & -1 & 2 \end{pmatrix}, \qquad L_{(1)} = \begin{pmatrix} 2 & -1 \\ -1 & 2 \end{pmatrix}, and \det(L_{(1)}) = 4 - 1 = 3. The triangle indeed has exactly three spanning trees, one for each edge left out. Applying the theorem to K_n recovers Cayley's formula n^{n-2}, since every labeled tree on n vertices is a spanning tree of K_n.

Necessity. Suppose G has an Euler circuit C. Every time C passes through a vertex v (other than at the very start/end, which is the same vertex for a circuit), it uses one edge to arrive at v and a different edge to leave v, since C never repeats an edge. So every visit to v accounts for exactly 2 of the edges at v, and since C uses every edge of G exactly once, \deg(v) must be even for every vertex v.

Sufficiency. Suppose G is connected and every vertex has even degree. Build a circuit by the following argument. Start at any vertex v_0 and follow edges, never reusing one, until stuck. Because every vertex has even degree, arriving at any vertex other than v_0 always leaves an unused edge to leave by (each visit uses up an "in" and an "out" edge in pairs, and the degree is even, so the walk cannot get stuck anywhere except back at v_0). So this walk is forced to return to v_0, forming a closed circuit C_1 using no edge twice.

If C_1 already uses every edge of G, it is the desired Euler circuit. Otherwise, since G is connected, some vertex w on C_1 has an unused edge incident to it. Remove the edges of C_1 from G; every vertex still has even degree in what remains (each vertex's degree dropped by an even amount — 0 or 2 — as C_1 passed through it). Repeat the same construction starting at w in the remaining graph to get a second closed circuit C_2 through w using only unused edges, then splice C_2 into C_1 at w (traverse C_1 up to w, detour around all of C_2, then finish C_1) to get a longer closed walk using no edge twice. Repeating this splicing process — always possible while unused edges remain, by connectivity — eventually uses every edge, producing an Euler circuit.

The trail case. If G has exactly two odd-degree vertices u and v, add a new edge \{u,v\} to form G^+ (a multigraph is fine here); every vertex of G^+ now has even degree, so G^+ has an Euler circuit by the case just proved. Deleting the added edge \{u,v\} from that circuit leaves an Euler trail of G from u to v. Conversely, an Euler trail from u to v in G forces \deg(u) and \deg(v) to be odd (the trail uses one unmatched edge at each endpoint) and every other vertex's degree to be even (same pairing argument as in necessity above), so exactly two vertices have odd degree.

Dirac's theorem is the special case of Ore's theorem (ores-theorem) where every single vertex, not just every non-adjacent pair, already meets half the degree bound: if \deg(v) \ge n/2 for every vertex v, then for any two vertices u,v (adjacent or not), \deg(u) + \deg(v) \ge \frac{n}{2} + \frac{n}{2} = n, so Ore's degree-sum condition holds for every non-adjacent pair in particular, and Ore's theorem gives a Hamiltonian cycle.

The self-contained argument (not leaning on Ore's theorem) runs identically to Ore's proof: assume for contradiction a maximal non-Hamiltonian graph G^+ \supseteq G on n vertices where every vertex still has degree \ge n/2 (adding edges only increases degrees), take a Hamiltonian path v_1 \cdots v_n guaranteed to exist between two non-adjacent vertices v_1, v_n of G^+, and note |A| + |B| = \deg(v_1) + \deg(v_n) \ge \frac{n}{2} + \frac{n}{2} = n > n - 1 for the index sets A = \{i : v_1 \sim v_i\} and B = \{i : v_n \sim v_{i-1}\}, both subsets of \{2,\dots,n\}. The pigeonhole overlap between A and B produces the same rotation — v_1 \cdots v_{i-1}\, v_n\, v_{n-1} \cdots v_i\, v_1 — that closes a Hamiltonian cycle, contradicting G^+'s assumed non-Hamiltonicity.

Suppose, for contradiction, that G satisfies the degree-sum condition but has no Hamiltonian cycle. Add edges to G one at a time — each new edge joining two non-adjacent vertices, which keeps the degree-sum condition true (degrees only go up) — for as long as the graph stays non-Hamiltonian, until no more edges can be added without creating a Hamiltonian cycle. Call the result G^+: a maximal non-Hamiltonian graph on n vertices still satisfying the degree-sum condition, where adding any missing edge creates a Hamiltonian cycle.

G^+ is not complete (a complete graph on n\ge3 vertices is trivially Hamiltonian), so pick two non-adjacent vertices u,v of G^+. Because G^+ is connected (the degree-sum condition with n\ge3 forces every vertex to have degree \ge 1, and a short argument rules out disconnected components under this bound) and not Hamiltonian, but adding edge \{u,v\} would create a Hamiltonian cycle, G^+ must already contain a Hamiltonian path v_1 v_2 \cdots v_n with v_1 = u and v_n = v (the only way adding one edge closes a Hamiltonian cycle is if a Hamiltonian path already runs between its two endpoints).

Consider the index sets A = \{\, i : v_i \text{ is adjacent to } v_1 \,\}, \qquad B = \{\, i : v_{i-1} \text{ is adjacent to } v_n \,\}. Both A and B are subsets of \{2, \dots, n\} (neither counts v_1 itself), so |A| = \deg(v_1) and |B| = \deg(v_n), and |A| + |B| = \deg(v_1) + \deg(v_n) \ge n by the degree-sum condition applied to the non-adjacent pair v_1, v_n. Since A, B \subseteq \{2,\dots,n\}, a set of size n-1, and |A|+|B| \ge n > n-1, the sets A and B must overlap: some index i lies in both.

That means v_1 is adjacent to v_i, and v_{i-1} is adjacent to v_n. But then v_1 \; v_2 \; \cdots \; v_{i-1} \; v_n \; v_{n-1} \; \cdots \; v_i \; v_1 is a Hamiltonian cycle of G^+: it follows the path from v_1 to v_{i-1}, jumps to v_n (valid, since v_{i-1} \sim v_n), follows the path backwards from v_n down to v_i, and closes back to v_1 (valid, since v_i \sim v_1) — using every vertex exactly once. This contradicts G^+ being non-Hamiltonian.

So no such maximal non-Hamiltonian G^+ can exist, and every graph satisfying the degree-sum condition is Hamiltonian.

Dirac's theorem as a corollary. If every vertex of G has \deg(v) \ge n/2, then for any two vertices u,v — adjacent or not — \deg(u) + \deg(v) \ge n/2 + n/2 = n, so Ore's condition holds in particular for every non-adjacent pair, and Dirac's theorem follows immediately from Ore's.

Both forms split into an easy inequality and a harder matching one; the edge form is proved here (the vertex form follows the same pattern, one level removed by splitting each vertex into an "in" and "out" copy joined by a unit-capacity edge).

Easy direction: max disjoint paths \le min cut. Let S be any u–v edge cut, and let P_1, \dots, P_k be any collection of pairwise edge-disjoint u–v paths. Every path P_i must use at least one edge of S (otherwise P_i would survive the removal of S, contradicting that S disconnects u from v). Since the paths are pairwise edge-disjoint, no single edge of S can be "used" by two different paths, so k \le |S|. Taking S to be a minimum cut gives (max disjoint paths) \le (min cut size).

Hard direction: min cut \le max disjoint paths. This direction is a direct consequence of the max-flow min-cut theorem. Build a flow network on the same vertex set as G, directing every edge both ways (or leaving G as-is if it is already directed) and giving every edge capacity 1, with source u and sink v. A flow of value k in this network that uses only integer edge-flows (guaranteed to exist at the maximum by the integrality of max-flow solutions on integer-capacity networks) decomposes into exactly k edge-disjoint u–v paths, since each edge carries at most 1 unit of flow and flow conservation forces every unit of flow entering a vertex (other than u,v) to leave along a different edge. By the max-flow min-cut theorem, this maximum flow value equals the capacity of a minimum u–v cut in the network — and because every edge has capacity 1, a minimum-capacity cut is exactly a minimum-size set of edges whose removal disconnects u from v. So \text{max edge-disjoint paths} = \text{max flow value} = \text{min cut capacity} = \text{min edge cut size}.

Combined with the easy direction, the two quantities are equal.

The full argument splits by connectivity; the key case is worked in detail and the general case is sketched, matching the level of most first courses.

Warm-up: why greedy coloring only guarantees \Delta + 1. Order the vertices any way and color greedily — each vertex has at most \Delta already-colored neighbors when its turn comes, so some color among \{1,\dots,\Delta+1\} is always free. Brooks' theorem says a smarter ordering saves one more color, except in the two exceptional families.

Case: G has a cut vertex (is not 2-connected). Split G at a cut vertex w into two smaller connected pieces G_1, G_2, each containing w and each with maximum degree at most \Delta. By induction (on the number of vertices), each G_i — unless it is itself a complete graph or odd cycle on \Delta+1 or fewer vertices, handled directly — is \Delta-colorable. Color G_1 and G_2 separately with \Delta colors, then permute G_2's color labels (a relabeling of colors never breaks a proper coloring) so that w gets the same color in both; the two colorings then glue into a proper \Delta-coloring of all of G, since G_1 and G_2 share only the vertex w.

Case: G is 2-connected, not complete, not an odd cycle. Pick any vertex r with a spanning tree of G rooted at r found by depth-first search, and order the remaining vertices v_1, \dots, v_{n-1} by decreasing distance from r in that tree (so r = v_n comes last). Every vertex v_i for i < n has at least one neighbor later in the order (its parent in the DFS tree), so when greedily coloring in this order, v_i has at most \Delta - 1 already-colored neighbors, always leaving a free color among \{1,\dots,\Delta\} — for every vertex except possibly r itself, which could have all \Delta neighbors already colored.

The theorem's real content is choosing r so that r also gets a free color. If G is not complete, some two neighbors x,y of some vertex r are themselves non-adjacent (otherwise every pair of vertices within distance 2 of each other would be pairwise adjacent, and 2-connectivity plus this "locally complete" property forces G = K_n, the excluded case). Root the DFS instead at r chosen so that x and y — two non-adjacent neighbors of r — get colored first and identically (possible because x,y are non-adjacent, so giving them the same color is proper), which frees up a color at r's turn: r has \Delta neighbors, but two of them (x,y) share one color, so at most \Delta - 1 distinct colors appear among r's neighbors, leaving a color free for r. (The 2-connectivity is exactly what's needed to guarantee this specific rooted DFS ordering exists and is well-defined; the odd-cycle exclusion handles the one remaining case where every vertex has degree exactly 2 and no such x,y pair with a usable ordering exists.) This completes a proper \Delta-coloring of G.

Bipartite \implies no odd cycle. Suppose G is bipartite with parts L and R, and let C = v_1 v_2 \cdots v_k v_1 be any cycle in G. Every edge of G joins a vertex of L to a vertex of R, so walking along C, consecutive vertices always alternate sides: if v_1 \in L then v_2 \in R, v_3 \in L, and so on, with v_i \in L exactly when i is odd. For C to close back up, v_k and v_1 must be on opposite sides too (since v_kv_1 is an edge), which forces k to be even. So every cycle of a bipartite graph has even length — no odd cycle exists.

No odd cycle \implies bipartite. Suppose G has no odd cycle; without loss of generality treat one connected component at a time; a graph is bipartite iff every component is, so let G (now connected) have no odd cycle. Fix any vertex r, and let L = \{\, v : d(r,v) \text{ is even} \,\}, \qquad R = \{\, v : d(r,v) \text{ is odd} \,\}, using graph distance d(r,v) (shortest-path length from r). This partitions all of G's vertices into L and R; the claim is that every edge of G joins L to R, making (L,R) a valid bipartition.

Suppose instead some edge \{u,v\} has both endpoints in the same part, say both in L, so d(r,u) and d(r,v) are both even. Take shortest paths P_u from r to u and P_v from r to v; let w be the last vertex where P_u and P_v agree (their paths coincide from r up through w, then diverge — w could be r itself). The two path segments from w to u and from w to v, together with the edge \{u,v\}, form a closed walk, and in fact a cycle (the two segments share only w, since w was the last shared vertex and both segments lie on shortest paths, which cannot revisit a vertex). Its length is \bigl(d(r,u) - d(r,w)\bigr) + \bigl(d(r,v) - d(r,w)\bigr) + 1, the two segment lengths plus the edge \{u,v\}. Since d(r,u) and d(r,v) are both even, and shortest-path lengths along a shared prefix force d(r,w) to have fixed parity relative to both (a standard shortest-path-tree fact — w lies on both shortest paths so d(r,u)-d(r,w) and d(r,v)-d(r,w) are the remaining segment lengths, which are both of the same parity as each other, since d(r,u) and d(r,v) share parity), the sum of the two segment lengths is even, and adding the one edge \{u,v\} makes the total cycle length odd — contradicting that G has no odd cycle. The same contradiction arises if both u,v \in R. So every edge joins L to R, and (L,R) is a proper bipartition of G.

Path P_n. Color the vertices in order along the path. The first vertex takes any of the k colors. Each later vertex must only avoid the color of the single neighbor already colored, leaving exactly k-1 choices regardless of which color that neighbor received. By the product rule, P(P_n,k) = k(k-1)^{n-1}.

Tree T. Root the tree anywhere and color vertices in any order that visits each vertex after its parent (for example, breadth-first). The root takes k colors; every other vertex has exactly one already- colored neighbor (its parent) to avoid, giving k-1 choices each. The count k(k-1)^{n-1} follows exactly as for the path — a path is just the special case of a tree with no branching.

Cycle C_n. Sequential coloring fails at the last vertex, whose two neighbors may or may not share a color, so we use deletion–contraction. Let e be any edge of C_n. Colorings of C_n - e (a path P_n) split into those where e's endpoints differ (proper colorings of C_n) and those where they agree (in bijection with proper colorings of the contraction C_n / e = C_{n-1}). Hence P(C_n,k) = P(P_n,k) - P(C_{n-1},k) = k(k-1)^{n-1} - P(C_{n-1},k). With base case P(C_3,k) = k(k-1)(k-2) = (k-1)^3 - (k-1), induction gives the closed form: assuming P(C_{n-1},k) = (k-1)^{n-1} + (-1)^{n-1}(k-1), P(C_n,k) = k(k-1)^{n-1} - (k-1)^{n-1} - (-1)^{n-1}(k-1) = (k-1)^n + (-1)^n(k-1) since k(k-1)^{n-1} - (k-1)^{n-1} = (k-1)^n and -(-1)^{n-1} = (-1)^n.

Induct on the number of edges e.

Base case. If G is a tree (no cycles), then e = v - 1 and the drawing has exactly f = 1 face — the one unbounded face, since a tree encloses no region. Then v - e + f = v - (v-1) + 1 = 2.

Inductive step. Suppose G is connected planar with e \ge v, so G contains a cycle (a connected graph with e < v is a tree, the base case). Pick any edge e_0 that lies on a cycle of G, and let G' = G - e_0. Because e_0 lies on a cycle, removing it does not disconnect G, so G' is still connected, planar (a sub-drawing of the same drawing), with v' = v vertices and e' = e - 1 edges.

Removing an edge that lies on a cycle merges the two faces on either side of that edge into one (an edge on a cycle always has two different faces on its two sides, since it bounds a closed region on at least one side), so f' = f - 1.

By the inductive hypothesis applied to G' (which has fewer edges), v' - e' + f' = 2 \implies v - (e-1) + (f-1) = 2 \implies v - e + f = 2, which is exactly the claim for G. By induction, the formula holds for every connected planar graph.

Necessity (the direction with an elementary proof): if G is planar, it contains no subdivision of K_5 or K_{3,3}. Two facts combine to give this direction directly.

First, K_5 and K_{3,3} are themselves non-planar. For K_5: a planar drawing of K_5 would need to satisfy Euler's formula (v-e+f=2 once subdivided into faces), but K_5 has v=5, e=10, and every face in a simple planar graph is bounded by at least 3 edges with each edge bordering at most 2 faces, forcing f \le 2e/3 = 20/3, i.e. f \le 6; Euler's formula would then need 5 - 10 + f = 2, i.e. f = 7 > 6, a contradiction. For K_{3,3}: it is bipartite, so every face boundary has length at least 4 (no odd cycles), forcing f \le 2e/4 = 2(9)/4 = 4.5, i.e. f \le 4; Euler's formula needs 6 - 9 + f = 2, i.e. f=5>4, again a contradiction.

Second, planarity is preserved both by taking subgraphs (deleting a vertex or edge from a planar drawing leaves a planar drawing) and by "un-subdividing" — replacing a path through degree-2 vertices with a single edge cannot introduce a crossing that wasn't already there. So if G contained a subdivision of K_5 or K_{3,3}, un-subdividing that piece would exhibit K_5 or K_{3,3} itself as a subgraph of a graph obtained from a subgraph of G, which would then have to be planar too — contradicting that K_5 and K_{3,3} are not planar. So a planar G can contain no such subdivision.

Sufficiency (the converse: no such subdivision implies planar) is the hard direction of this theorem — first proved by Kuratowski in 1930 — and requires a substantial case analysis (typically via a minimal counterexample argument over 3-connected components) that is beyond the scope of a first course; it is stated here without proof, as is standard even in dedicated graph theory texts.

Planar \implies a dual exists (construction). Fix a plane embedding of G with face set F. Build G^* by placing one vertex f^* inside each face f \in F, and for every edge e of G bordering faces f_1, f_2 (possibly f_1 = f_2, when e has the same face on both sides), draw an edge f_1^* f_2^* crossing e exactly once and no other edge of G. This is always possible without new crossings — draw each dual edge in a small neighborhood of the primal edge it crosses, staying inside the two bordering faces — so G^*, drawn this way, is itself a planar graph and by construction is a dual of G.

A dual existing \implies G is planar. Suppose G has some abstract dual G^* — a graph on the edge set of G (up to the standard correspondence) satisfying the defining relation between G's cycles and G^*'s cuts (every cycle of G corresponds to a minimal edge cut of G^*, and vice versa). This structural relation forces G's cycle space to be realizable as a set of face boundaries with the Jordan curve separation property that a planar embedding requires — in particular, it rules out G containing a subdivision of K_5 or K_{3,3}, since neither of those graphs admits a consistent cycle/cut pairing of this kind (a short case check on their cycle structure shows no dual satisfying the relation can exist for either). By Kuratowski's theorem, a graph with no K_5 or K_{3,3} subdivision is planar, so G is planar. (This direction is Whitney's own 1932 theorem connecting abstract duality to planarity; the full case analysis behind the Kuratowski-obstruction argument is the technical heart of the original proof and is only sketched here.)

Induct on the number of vertices n. For n \le 5, at most 5 colors are trivially enough (one color per vertex). Assume every planar graph on fewer than n vertices is 5-colorable, and let G be planar with n vertices.

Step 1: G has a vertex of degree at most 5. Fix any plane embedding of G. If every vertex had degree \ge 6, the handshaking theorem would give 2e = \sum_v \deg(v) \ge 6n, i.e. e \ge 3n. But a simple planar graph always satisfies e \le 3n - 6 (the edge bound following from Euler's formula), and 3n > 3n - 6 is impossible to satisfy simultaneously — contradiction. So some vertex v has \deg(v) \le 5.

Step 2: color G - v and reinsert v. G - v is planar with n-1 vertices, so by the inductive hypothesis it has a proper 5-coloring. If v's neighbors (at most 5 of them) use at most 4 distinct colors among themselves, some color is free for v and the coloring extends immediately.

Step 3: the hard case — \deg(v) = 5 and all 5 neighbors have distinct colors 1,2,3,4,5 (in clockwise order around v in the plane embedding). This is the one case needing an extra idea: a Kempe chain argument. Look at the subgraph of G-v induced by only the vertices colored 1 or 3. Let u_1 be v's neighbor colored 1 and u_3 be v's neighbor colored 3.

If u_1 and u_3 lie in different connected components of this 1/3-colored subgraph: swap colors 1 \leftrightarrow 3 throughout u_1's component only. This is still a proper coloring of G-v (the swap only touches vertices colored 1 or 3 inside one component, consistently), and now u_1 is colored 3 — so v's neighbors only use colors 2,3,3,4,5, freeing color 1 for v.

If u_1 and u_3 lie in the same component (connected by a path alternating colors 1,3,1,3,\dots): that path, together with the two edges v–u_1 and v–u_3, forms a cycle enclosing either v's neighbor colored 2 or the one colored 4 (by the Jordan curve theorem, since the embedding is planar — the alternating 1/3 path together with v separates the plane, and going around v's neighbors in order 1,2,3,4,5, exactly one of 2,4 is trapped inside this loop and the other stays outside). Say the vertex colored 4 is trapped outside instead — then repeat the same Kempe-chain swap using colors 2 and 4 instead: v's neighbors colored 2 and 4 cannot be connected by a 2/4-alternating path (any such path would have to cross the already- established 1/3 chain, impossible in a planar drawing), so the different-component case applies to the 2,4 pair, and swapping frees color 2 or 4 for v instead.

Either way, v can be given a color from \{1,\dots,5\} not used by any of its neighbors, extending the 5-coloring of G-v to all of G. By induction, every planar graph is 5-colorable.

Weak duality: every flow value is at most every cut's capacity. Let f be any s–t flow with value |f|, and let (S,T) be any s–t cut. By flow conservation, the net flow out of S equals |f| (summing conservation at every vertex of S except s makes all internal-to-S terms cancel, leaving exactly the net flow crossing the cut). That net flow out of S is at most the total capacity of edges from S to T (flow on each such edge is capped at its capacity, and flow on edges from T back into S only subtracts, never adds, to the net). So |f| \le \sum_{e:\, S\to T} c(e) = \text{cap}(S,T) for every flow f and every cut (S,T); in particular, the maximum flow value is at most the minimum cut capacity.

Equality is achieved. Run the Ford–Fulkerson method to a maximum flow f^* (termination and correctness of reaching a maximum assumed from the algorithm's own analysis). Because f^* is maximum, its residual graph G_{f^*} has no augmenting path from s to t. Let S be the set of all vertices reachable from s in G_{f^*}, and T everything else; s \in S and t \in T (since no augmenting path reaches t), so (S,T) is a valid s–t cut.

For every edge e from S to T in the original network, f^*(e) = c(e) — otherwise e would have residual capacity left, putting its head in S's reachable set too, contradicting that it's in T. For every edge from T to S, f^*(e) = 0 by the same reasoning applied to the reverse residual edge (a positive flow on a T \to S edge would create a residual edge S-side back into T, again contradicting the reachability boundary). So the net flow across (S,T) is exactly \sum_{e:\, S\to T} c(e) - \sum_{e:\, T \to S} 0 = \text{cap}(S,T), and by flow conservation this net flow equals |f^*|. So |f^*| = \text{cap}(S,T) \ge min cut capacity, and combined with weak duality (|f^*| \le min cut capacity, since |f^*| is a flow value), |f^*| = \text{cap}(S,T) = \text{min cut capacity}. So the maximum flow value equals the minimum cut capacity, exhibited by this specific (S,T).

Necessity. Suppose a matching M saturates L, and let S \subseteq L be any subset. Each vertex of S is matched by M to its own vertex of R, and these matched partners are distinct because no two edges of a matching share an endpoint. Every matched partner of a vertex in S is, in particular, a neighbor of that vertex, so all |S| of them lie in N(S). Hence |N(S)| \ge |S|. Equivalently: if some set S has |N(S)| < |S|, the |S| vertices of S would need distinct partners drawn from fewer than |S| available neighbors, which is impossible — the deficiency |S| - |N(S)| counts vertices of S that must go unmatched.

Sufficiency (sketch). Suppose |N(S)| \ge |S| for every S \subseteq L, and let M be a matching of maximum size. If M did not saturate L, pick an unmatched vertex u \in L and consider all vertices reachable from u by alternating paths (paths whose edges alternate between non-matching and matching edges). Let A \subseteq L and B \subseteq R be the reachable vertices on each side. A standard argument shows every vertex of B is matched (otherwise an augmenting path would let us enlarge M, contradicting maximality) and that B = N(A) with each vertex of A \setminus \{u\} matched into B. Counting then gives |N(A)| = |B| = |A| - 1 < |A|, violating Hall's condition. So M saturates L. The full details of the reachability argument are the standard augmenting-path proof of the theorem.

Each edge e = \{u, v\} of G has exactly two endpoints, u and v (a loop at v is the case u = v, still contributing two to that one vertex's degree count, which is exactly why a loop is defined to add 2 to \deg(v) rather than 1). Build the sum \sum_{v\in V}\deg(v) by counting, for every edge, how many times that edge gets counted across the whole sum.

Fix one edge e=\{u,v\}. It is counted once when computing \deg(u) (since e is incident to u) and once more when computing \deg(v) (since e is also incident to v), and it is never counted in any other vertex's degree, since e touches no vertex besides u and v. So every edge contributes exactly 2 to the total \sum_{v\in V}\deg(v), and there are |E| edges, giving \sum_{v \in V} \deg(v) = \sum_{e \in E} 2 = 2|E|.

The odd-degree count is even. Split V into V_{\text{even}} (even degree) and V_{\text{odd}} (odd degree). Then \sum_{v \in V_{\text{even}}} \deg(v) + \sum_{v \in V_{\text{odd}}} \deg(v) = 2|E|, an even number. The first sum is a sum of even numbers, so it's even. Subtracting an even number from an even number leaves an even number, so \sum_{v \in V_{\text{odd}}} \deg(v) is even too. A sum of odd numbers is even only when there is an even count of them (an odd count of odd numbers always sums to something odd), so |V_{\text{odd}}| itself must be even.

Sanity check: a triangle (3 vertices, each of degree 2) has degree sum 2+2+2=6, and 2|E| = 2(3) = 6 -- matches, and 0 vertices have odd degree, which is indeed even.

The full argument splits by connectivity; the key case is worked in detail and the general case is sketched, matching the level of most first courses.

Warm-up: why greedy coloring only guarantees \Delta + 1. Order the vertices any way and color greedily — each vertex has at most \Delta already-colored neighbors when its turn comes, so some color among \{1,\dots,\Delta+1\} is always free. Brooks' theorem says a smarter ordering saves one more color, except in the two exceptional families.

Case: G has a cut vertex (is not 2-connected). Split G at a cut vertex w into two smaller connected pieces G_1, G_2, each containing w and each with maximum degree at most \Delta. By induction (on the number of vertices), each G_i — unless it is itself a complete graph or odd cycle on \Delta+1 or fewer vertices, handled directly — is \Delta-colorable. Color G_1 and G_2 separately with \Delta colors, then permute G_2's color labels (a relabeling of colors never breaks a proper coloring) so that w gets the same color in both; the two colorings then glue into a proper \Delta-coloring of all of G, since G_1 and G_2 share only the vertex w.

Case: G is 2-connected, not complete, not an odd cycle. Pick any vertex r with a spanning tree of G rooted at r found by depth-first search, and order the remaining vertices v_1, \dots, v_{n-1} by decreasing distance from r in that tree (so r = v_n comes last). Every vertex v_i for i < n has at least one neighbor later in the order (its parent in the DFS tree), so when greedily coloring in this order, v_i has at most \Delta - 1 already-colored neighbors, always leaving a free color among \{1,\dots,\Delta\} — for every vertex except possibly r itself, which could have all \Delta neighbors already colored.

The theorem's real content is choosing r so that r also gets a free color. If G is not complete, some two neighbors x,y of some vertex r are themselves non-adjacent (otherwise every pair of vertices within distance 2 of each other would be pairwise adjacent, and 2-connectivity plus this "locally complete" property forces G = K_n, the excluded case). Root the DFS instead at r chosen so that x and y — two non-adjacent neighbors of r — get colored first and identically (possible because x,y are non-adjacent, so giving them the same color is proper), which frees up a color at r's turn: r has \Delta neighbors, but two of them (x,y) share one color, so at most \Delta - 1 distinct colors appear among r's neighbors, leaving a color free for r. (The 2-connectivity is exactly what's needed to guarantee this specific rooted DFS ordering exists and is well-defined; the odd-cycle exclusion handles the one remaining case where every vertex has degree exactly 2 and no such x,y pair with a usable ordering exists.) This completes a proper \Delta-coloring of G.

Suppose, for contradiction, that every one of the m boxes holds at most one object. Then the total number of objects placed is at most m \cdot 1 = m. But n objects were placed, and n > m, so n \leq m and n > m both hold — an impossibility. So some box must hold at least 2 objects.

The general form follows the same contradiction. If every box held strictly fewer than \lceil n/m \rceil objects, each box would hold at most \lceil n/m \rceil - 1 objects, giving a total of at most m\bigl(\lceil n/m \rceil - 1\bigr) < n objects placed — contradicting that all n objects were placed somewhere.