MATH 371

Let $S = \sum_{v \in V} \deg(v)$. Each edge $\{u,v\}$ contributes +1 to $\deg(u)$ and +1 to $\deg(v)$, so contributes exactly 2 to $S$. Therefore $S = 2|E|$. ∎

Corollary: Since $2|E|$ is even, the number of odd-degree vertices must be even.

Strong induction on walk length $k$.
Base: $k \le 2$: no room for repeated vertex, so walk is already a path.
Step: If $w_j = w_r$ for $j < r$, skip $w_{j+1}, \ldots, w_r$ to get a shorter walk. By induction, it contains a path. ∎

(⇒) Bipartite ⇒ parts $X, Y$, every edge crosses. Any cycle alternates $X, Y, X, Y\ldots$ — to return to the start set, must have even length.
(⇐) No odd cycles ⇒ pick $v$, set $X = \{$even-dist from $v\}$, $Y = \{$odd-dist$\}$. If two in $X$ were adjacent, their paths + that edge create an odd cycle. Contradiction. ∎

$\\text{rad}(G) \\le \\text{diam}(G)$ is true by definition (min $\\le$ max).
For $\\text{diam}(G) \\le 2 \\cdot \\text{rad}(G)$: let $c$ be a center vertex, $u$ and $v$ the farthest pair:
$\\text{diam}(G) = d(u,v) \\le d(u,c) + d(c,v) \\le 2 \\cdot \\text{ecc}(c) = 2 \\cdot \\text{rad}(G)$. ∎

Construct $H$ by adding 4 new vertices $w, x, y, z$ to $G$. Connect $w-x$ and $y-z$. Connect $x$ and $y$ to every vertex in $G$.
Now in $H$: any $v \\in G$ has $\\text{ecc}(v)=2$. $\\text{ecc}(x)=\\text{ecc}(y)=3$, and $\\text{ecc}(w)=\\text{ecc}(z)=4$. So $G$ uniquely rests at the center! ∎

$(\\impliedby)$ If all have ecc 1, $G$ is complete and is its own periphery. If none have ecc 1, add a single universal vertex $w$. Now $w$ has ecc 1, and all of $G$ has ecc 2, making $G$ the periphery.
$(\\implies)$ Discarding the mixed case: if some but not all vertices had ecc 1, you can't push the entire graph $G$ out to the same periphery distance because the ecc 1 vertices will always be closer to the center than the others. ∎

Induction on $k$. Base: $k=1$, $A^1=A$, $(i,j)$ is 1 if edge exists, 0 otherwise.
Step: A $k$-walk from $v_i$ to $v_j$ is a $(k-1)$-walk from $v_i$ to some $v_h$, plus edge $v_h \\to v_j$. Summing $[A^{k-1}]_{ih} \\cdot A_{hj}$ over all $h$ is exactly the formula for matrix multiplication $[A^k]_{ij}$. ∎

For all $i,j$, $[S_k]_{j,i} > 0$ iff there is a walk from $v_j$ to $v_i$ of length at most $k$ (because $S_k = I + A + \cdots + A^k$ accumulates walk counts).

(1) Eccentricity: The first $k$ where row $j$ has no zeros means $v_j$ can reach every vertex within $k$ steps, and this fails for $k-1$. Hence $\text{ecc}(v_j)=k$.

(2) Radius: Radius is the minimum eccentricity, so it is the first $r$ where some row becomes strictly positive.

(3) Diameter: Diameter is the maximum eccentricity, so it is the first $m$ where every row (equivalently every entry) is strictly positive. ∎

Strong induction on $n$.
Base: $n=1$: 0 edges. ✓
Step: Remove any edge $e$. Tree splits into $T_1, T_2$ with $k_1 + k_2 = k$ vertices. By hypothesis: $(k_1-1) + (k_2-1) + 1 = k - 1$ edges. ∎

Each component $T_i$ is a tree with $n_i$ vertices $\\implies n_i - 1$ edges.
Total edges = $\\sum (n_i - 1) = (\\sum n_i) - k = n - k$. ∎

1.12 (Connected + $n-1$ edges): If it had a cycle, you could remove an edge without breaking connectivity until it becomes a tree. But that resulting tree would have strictly fewer than $n-1$ edges, which is impossible.
1.13 (Acyclic + $n-1$ edges): Acyclic means it's a forest with $k$ components. Edges = $n-k$. But we are given edges = $n-1$. Therefore $k=1$, meaning it's connected. ∎

Let $P=u_0,u_1,\ldots,u_\ell$ be a longest path in $T$.

Suppose $\deg(u_0)\ge 2$. Then $u_0$ has a neighbor $w\neq u_1$. In a tree, $w$ cannot be elsewhere on $P$ (that would create a cycle), so $w\notin V(P)$. Then $w,u_0,u_1,\ldots,u_\ell$ is a path longer than $P$, contradiction.

So $\deg(u_0)=1$, i.e. $u_0$ is a leaf. The same argument at $u_\ell$ shows $\deg(u_\ell)=1$. Therefore $T$ has at least two leaves. ∎

Removing all leaves decreases every remaining vertex's eccentricity by exactly 1. Since all eccentricities shift uniformly, the minimizer (center) is preserved. Eventually you reach $K_1$ or $K_2$. ∎

Proof by induction on $k$:

• Base: $k = 0 \Rightarrow T = K_1$ (single vertex), trivially a subgraph. $k = 1 \Rightarrow T = K_2$, and $\delta(G) \ge 1$ means $G$ has at least one edge.
• Inductive step: Assume true for trees with $k-1$ edges.
  • $T$ has a leaf $v$ (by Theorem 1.14). Let $w$ be its neighbor.
  • $T - v$ has $k-1$ edges. Since $\delta(G) \ge k \ge k-1$, by induction $T - v$ is a subgraph of $G$.
  • In $G$, vertex $w$ (from the copy of $T-v$) has degree $\ge k$, but only $k-1$ vertices of $T-v$ are using its edges. So $w$ has a neighbor $u$ outside the copy.
  • Attach $u$ as the leaf $\Rightarrow$ we've found $T$ inside $G$. ∎

Proof by contradiction:

• Let $T$ = Kruskal's result, with edges added as $e_1, e_2, \dots, e_{n-1}$.
• Assume $T$ is not an MST. Pick the MST $T'$ that agrees with $T$ for the most edges.
• Let $e_{k+1}$ be the first edge where they differ ($T'$ has $e_1, \dots, e_k$ but not $e_{k+1}$).
• Adding $e_{k+1}$ to $T'$ creates a cycle $C$. This cycle has an edge $e' \notin T$ (since $T$ has no cycles).
• Kruskal's chose $e_{k+1}$ before $e'$, so $w(e_{k+1}) \le w(e')$.
• Swap: $T' + e_{k+1} - e'$ is a spanning tree with weight $\le$ weight of $T'$, and it agrees with $T$ on one more edge — contradicting our choice of $T'$! ∎

Proof via Prüfer sequences (bijection).

Tree $\to$ sequence: Repeat $n-2$ times: choose the smallest labeled leaf, record its neighbor, then delete that leaf.

Sequence $\to$ tree: Start with labels $A=\{1,\dots,n\}$. Reading the sequence left to right, each step connects the smallest label in $A$ not appearing later in the sequence to the current sequence entry, then removes that leaf label from $A$. When the sequence ends, connect the last two labels in $A$.

These constructions are inverse to each other, so labeled trees on $n$ vertices are in bijection with sequences of length $n-2$ over $\{1,\dots,n\}$. Therefore the count is $$n^{n-2}.$$ Also, each vertex $v$ appears exactly $\deg(v)-1$ times in the Prüfer sequence, so sequence length is $$\sum_{v}(\deg(v)-1)=2(n-1)-n=n-2.$$ ∎

The recipe:

1. Build A (adjacency matrix) and D (diagonal matrix of degrees)
2. Compute $L = D - A$ (called the Laplacian)
3. Delete any one row and matching column from $L$
4. The determinant of what's left = number of spanning trees

Proof framework:
Let $G$ have $n$ vertices and $k$ edges. Define the incidence matrix $N$ ($n \times k$): $[N]_{i,j} = 1$ if vertex $v_i$ touches edge $f_j$, else 0. Each column has exactly two 1s.
Create $M$ from $N$ by flipping the top 1 in each column to $-1$ (directed edges).

Claim A: $MM^T = D - A$.
- Diagonal $(i=j)$: counts degrees.
- Off-diagonal (edge): $+1 \cdot -1 = -1$.
- Off-diagonal (no edge): 0.

Claim B: Take any subgraph $H$ with $n$ vertices and $n-1$ edges. Delete row $p$ from $M$, keep only columns for $H$'s edges to get $M'$.
- If $H$ is a tree: $|\det(M')| = 1$
- If $H$ is not a tree: $\det(M') = 0$

Putting it together:
Since all row/column sums of $D-A$ are 0, all cofactors are equal. Pick the $(1,1)$ cofactor:
$\det((D-A)_{(1|1)}) = \det(M_1 M_1^T)$
By the Cauchy-Binet formula, this equals the sum of $\det(M')^2$ over all $(n-1)$-column subsets. Each spanning tree contributes $1^2 = 1$ and non-trees contribute 0. $\Rightarrow$ Cofactor = number of spanning trees. ∎

(1 $\Rightarrow$ 2) In an Eulerian circuit, each visit to a vertex uses one entering and one leaving edge. Edges at every vertex are paired, so every $\deg(v)$ is even.

(2 $\Rightarrow$ 3) Induct on $|E|$. If all degrees are even and $G$ is connected, $G$ contains a cycle $C$. Remove edges of $C$. Remaining components still have all even degrees; by induction each component's edges partition into cycles. Add back $C$ to get a cycle partition of $E(G)$.

(3 $\Rightarrow$ 1) Take a longest circuit formed by splicing cycles from the partition. If unused edges remain, connectivity gives an unused cycle meeting the circuit at some vertex; splice it in to obtain a longer circuit, contradiction. Hence one circuit uses every edge, so $G$ is Eulerian. ∎

Corollary (Euler trail): A connected graph has an Euler trail iff it has at most two odd-degree vertices.

Using proof by contradiction:

1. Assume the Opposite: Suppose we have a graph where every vertex has degree $\ge n/2$, but there is no Hamiltonian cycle.
2. The Longest Path: Let $P$ be the longest possible path in this graph, starting at $v_1$ and ending at $v_p$.
3. Endpoints Must Stay on the Path: Because $P$ is already the "longest," the neighbors of start ($v_1$) and end ($v_p$) must be vertices that are already on that path. If they connected outside, the path could be longer!
4. The "Folding" Trick: Since $v_1$ and $v_p$ each have at least $n/2$ neighbors on this path, pigeonhole logic proves there must be a spot in the middle where $v_1$ is connected to one vertex ($v_{j+1}$) and $v_p$ is connected to the vertex right before it ($v_j$).
5. Creating the Cycle: This "crossing" allows you to re-route the path into a cycle.
6. The Contradiction: If this cycle doesn't include every vertex, the high degree condition ($\ge n/2$) would actually let us find a way to make a path even longer than our "longest path." This is impossible, so our original assumption was wrong. A Hamiltonian cycle must exist. ∎

The Goal: Prove that if $\deg(u)+\deg(v) \ge n$ for all nonadjacent vertices, $G$ is Hamiltonian.

Step 1: Create a "Maximum" Non-Hamiltonian Graph: Assume there is a graph $G$ that follows the rule but is not Hamiltonian. We add edges one by one until it is impossible to add another without creating a Hamiltonian cycle. Call this $\overline{G}$.

Step 2: Find the Longest Path: Since $\overline{G}$ is not Hamiltonian, there must be two nonadjacent spots, $u$ and $v$. But adding a road between them would have finished the circle, so there must already be a Hamiltonian path from $u$ to $v$. We label them: $u=v_1, v_2, \dots, v_n=v$.

Step 3: The Impossible Connection (Lemma): If $u$ connects to $v_{i+1}$, then $v$ cannot connect to $v_i$. Why? We could walk $u \to v_{i+1} \dots v \to v_i \dots u$, forming a cycle!

Step 4: Counting the Roads:
- Let $U$ be the set of spots $v_i$ where $u$ connects to $v_{i+1}$. $|U| = \deg(u)$.
- Let $V$ be the spots where $v$ connects to $v_i$. $|V| = \deg(v)$.
By Step 3, $U$ and $V$ cannot overlap. They can only map to the $n-1$ other spots, so combined connections $\le n-1$.
$\deg(u)+\deg(v) \le n-1$
Logical Conclusion: We assumed $\deg(u)+\deg(v) \ge n$, creating a contradiction. ∎

Look at the longest cycle $C$ and an excluded vertex $v$. The component $H$ containing $v$ connects to $C$ via $r$ "gatekeeper" vertices. $r$ must be $\ge \kappa(G)$. The vertices immediately following these gatekeepers on $C$ form a set $S$ with $v$. Size of $S$ is $\ge \kappa(G) + 1 \ge \alpha(G) + 1$. Thus, two vertices in $S$ must be adjacent (since $|S| > \alpha$). This creates a detour that makes the cycle longer, contradicting that $C$ was the longest! ∎

Assume $C$ is the longest cycle, but not Hamiltonian. Because $G$ is 2-connected, there's a vertex $v \notin C$ attached to some $w \in C$. Look at $w$'s neighbours on the cycle: $a$ (before) and $b$ (after). Neither $a$ nor $b$ can connect to $v$, otherwise we get a longer cycle detour.

If $a$ is not connected to $b$, the vertices $\{w, v, a, b\}$ form a perfect claw $K_{1,3}$ centered at $w$. Contradiction!
If $a$ is connected to $b$, the vertices $\{w, v, a, b\}$ form a $Z_1$ graph. Contradiction!
Therefore, $C$ must have been Hamiltonian all along. ∎

Induction on $F$. Base ($F=1$): If there's only 1 face, there are no cycles. The graph is a tree. By Thm 1.10, $E = V - 1$. So $V - (V - 1) + 1 = 2$. Checks out.
Step: If $F > 1$, there must be a cycle. Pick any edge $e$ on a cycle and remove it. The graph remains connected, but two faces merge into one ($F \to F-1$), and we lost one edge ($E \to E-1$). Vertices $V$ remain the same. The quantity $V - E + F$ stays perfectly balanced! By induction, the new graph satisfies it, so the old one must too. ∎

Suppose $K_{3,3}$ is planar. Then $n=6, q=9$. By Euler's Formula:
$r = 2 - n + q = 2 - 6 + 9 = 5 \text{ faces}$

Now count boundary edges. Let $C$ = total count of (face, edge) pairs where the edge borders the face. Each edge borders at most 2 faces, so:
$C \le 2q = 2 \times 9 = 18$

Since $K_{3,3}$ is bipartite, it has no triangles. Every face is bounded by at least 4 edges (shortest cycle in a triangle-free graph is 4). So:
$C \ge 4r = 4 \times 5 = 20$

But $C \le 18$ and $C \ge 20$ is impossible. Contradiction. $K_{3,3}$ is nonplanar! ∎

Let $C$ = total count of (face, edge) boundary pairs.
Since every face is bounded by at least 3 edges (no self-loops, $n \ge 3$, minimum cycle is 3):
$C \ge 3r$

Since each edge borders at most 2 faces:
$C \le 2q$

Combining: $3r \le 2q$. Substitute Euler's formula $r = 2 - n + q$:
$3(2 - n + q) \le 2q$
$6 - 3n + 3q \le 2q$
$q \le 3n - 6$ ∎

Bonus: Equality holds exactly when every face is a triangle (maximal planar/triangulation).

$K_5$ has $n = 5$ and $q = 10$.
By Theorem 1.33, a planar graph on 5 vertices has bounded edges: $q \le 3(5) - 6 = 9$.
Since $10 > 9$, $K_5$ is nonplanar. ∎

What went wrong without Thm 1.33? Without that bound, we'd have to try drawing $K_5$ in every possible way and check each one. Thm 1.33 gives a clean one-line shortcut.

Suppose for contradiction that every vertex of $G$ has degree $\ge 6$. Then:
$\sum_{v \in V} \deg(v) \ge 6n$

But $\sum \deg(v) = 2q$ (Handshaking Lemma), so $2q \ge 6n$, meaning $q \ge 3n$.
But this contradicts Theorem 1.33: planar graphs must have $q \le 3n - 6$.
Therefore some vertex must have degree $\le 5$. ∎

Lower bound ($\rho(P) \ge 3$): A polygon needs at least 3 edges to enclose an area.

Upper bound ($\rho(P) \le 5$): Assume for contradiction every face has $\ge 6$ edges. Total boundary count $\sum \text{sides} \ge 6F$. This total equals $2E$ (each edge borders 2 faces), so $6F \le 2E \Rightarrow E \ge 3F$.

Similarly, each vertex has degree $\ge 3$ (must be a 3D corner), so sum of degrees $\ge 3V$. This equals $2E$, giving $V \le 2E/3$.
Substitute into Euler's formula $V - E + F = 2$:
$2 = V - E + F \le \frac{2}{3}E - E + \frac{1}{3}E = 0$
$2 \le 0$ — contradiction! ∎

Let $P$ have $V$ vertices, $E$ edges, $F$ faces, with $k$ edges per face and $r$ faces per vertex.

Two counting facts:
- Each face has $k$ edges, shared by 2 faces: $kF = 2E$
- Each vertex has $r$ edges, shared by 2 vertices: $rV = 2E$

Substitute $V = 2E/r$ and $F = 2E/k$ into Euler's Formula $V - E + F = 2$:
$2E/r - E + 2E/k = 2$
Divide by $2E$:
$1/r - 1/2 + 1/k = 1/E$
Since $1/E > 0$, we get $1/r + 1/k > 1/2$, or equivalently $2/r + 2/k > 1$.

From Thm 1.37: $3 \le k \le 5$. And $r \ge 3$ for a 3D corner. Enumerate all combinations:
- $k=3, r=3$: sum = $4/3 > 1$ (Tetrahedron)
- $k=3, r=4$: sum = $7/6 > 1$ (Octahedron)
- $k=3, r=5$: sum = $16/15 > 1$ (Icosahedron)
- $k=4, r=3$: sum = $7/6 > 1$ (Cube)
- $k=5, r=3$: sum = $16/15 > 1$ (Dodecahedron)
All other combinations give $\le 1$. Exactly 5 solutions exist. ∎

What is a "subdivision"? Take a graph and "stretch" edges by inserting degree-2 vertices. Subdividing doesn't change planarity.

The two directions:
- Easy ($\Rightarrow$): If $G$ is planar, it obviously can't contain a subdivision of $K_5$ or $K_{3,3}$, since those are nonplanar and a planar graph can't contain a nonplanar subgraph.
- Hard ($\Leftarrow$): If $G$ has no subdivision of $K_5$ or $K_{3,3}$ hidden in it, then $G$ must be planar. This is the remarkable and deep part — you just need to check for these two obstructions.

Application: To prove the Petersen graph is nonplanar, pick 6 specific vertices and find 9 internally vertex-disjoint paths connecting them exactly like a $K_{3,3}$! By Kuratowski's theorem, it is nonplanar. ∎

Order vertices arbitrarily as $v_1,\ldots,v_n$, and color greedily in that order.

When coloring $v_i$, it has at most $\Delta(G)$ neighbors total, so among already-colored vertices, at most $\Delta(G)$ colors are forbidden. Using a palette of $\Delta(G)+1$ colors, at least one color remains available for $v_i$.

Proceeding through all vertices yields a proper coloring with at most $\Delta(G)+1$ colors. Therefore $\chi(G)\le \Delta(G)+1$. ∎

Case 1: $G$ not 2-connected. Then $G$ has a cut vertex; color each block with at most $\Delta(G)$ colors and match colors at shared cut vertices. This gives a global $\Delta(G)$-coloring.

Case 2: $G$ 2-connected, not complete, not an odd cycle. Choose a vertex $v$ of degree $\Delta$, and two nonadjacent neighbors $u,w$ of $v$. Order vertices so $u=v_1$, $w=v_2$, $v=v_n$, and every intermediate vertex has a later neighbor. Color greedily in this order, first giving $u,w$ the same color.

For each intermediate vertex, at least one neighbor is uncolored, so at most $\Delta-1$ neighbor colors are forbidden; one of $\Delta$ colors is free. At the last vertex $v$, its $\Delta$ neighbors include $u,w$ with the same color, so at most $\Delta-1$ distinct colors appear around $v$; one color is free for $v$. Hence $\chi(G)\le\Delta(G)$. ∎

Lower bound: In any proper coloring with $\chi(G)$ colors, each color class is an independent set, so each class has size at most $\alpha(G)$. Therefore $$n \le \chi(G)\,\alpha(G)\quad\Rightarrow\quad \chi(G)\ge \frac{n}{\alpha(G)}.$$ Upper bound: Let $S$ be a maximum independent set with $|S|=\alpha(G)$. Color all vertices of $S$ with one color. Color each of the remaining $n-\alpha(G)$ vertices with a distinct fresh color. Total colors used: $$1+(n-\alpha(G))=n+1-\alpha(G).$$ Hence $\chi(G)\le n+1-\alpha(G)$. ∎

Induction on $n$. By Thm 1.35, $\exists v$ with $\deg(v)\le 5$. Remove $v$, 5-color $G-v$.
If $\deg(v)\le 4$: at most 4 colors used → 5th is free.
If $\deg(v)=5$, all 5 colors used: Kempe chain swap on colors 1-3. If $v_1, v_3$ in different components → swap frees color 1. If same → the 1-3 path separates $v_2$ from $v_4$ → swap 2-4 frees color 2. ∎

Let $e=\{u,v\}$. Consider all proper $k$-colorings of $G-e$, and split them into two disjoint classes:
• Class A: $u\ne v$. These are exactly the proper colorings of $G$ (since adding edge $e$ enforces $u\ne v$).
• Class B: $u=v$. These are exactly the proper colorings of $G/e$ (contracting $e$ forces $u,v$ to share one color).

So $$C_{G-e}(k)=C_G(k)+C_{G/e}(k),$$ and rearranging gives $$C_G(k)=C_{G-e}(k)-C_{G/e}(k).$$ ∎

Use induction via deletion-contraction: $$C_G = C_{G-e} - C_{G/e}.$$ Deletion keeps $n$ vertices; contraction has $n-1$ vertices. This gives:
(1) degree is $n$.
(2) leading coefficient is $1$ (from repeated deletions down to edgeless graph).
(3) coefficient of $k^{n-1}$ is $-q$ (each edge contributes one subtraction at that level).
(4) $C_G(0)=0$ since no graph has a proper 0-coloring.
(5) signs alternate by the recursive subtraction pattern in deletion-contraction. ∎

Induction on $n$.
Base ($n=3$): $C_3=K_3$, so $$C_{C_3}(k)=k(k-1)(k-2)=(k-1)^3-(k-1),$$ matching $(k-1)^n+(-1)^n(k-1)$ at $n=3$.

Step: Assume true for $C_{n-1}$. In $C_n$, let $e=\{v_1,v_n\}$. By deletion-contraction: $$C_{C_n}(k)=C_{C_n-e}(k)-C_{C_n/e}(k).$$ Now $C_n-e=P_n$, so $C_{P_n}(k)=k(k-1)^{n-1}$, and $C_n/e=C_{n-1}$. Thus $$C_{C_n}(k)=k(k-1)^{n-1}-\Big((k-1)^{n-1}+(-1)^{n-1}(k-1)\Big)$$ $$=(k-1)^n+(-1)^n(k-1).$$ Hence the formula holds for all $n\ge 3$. ∎

($\Rightarrow$ "aug path $\Rightarrow$ not max"):
If augmenting path $P$ exists, flip all edges along $P$. The path has one more non-$M$ edge than $M$-edge (both endpoints are free), so flipping gives $|M|+1$ edges. $M$ wasn't maximum.

($\Leftarrow$ "no aug path $\Rightarrow$ max"):
Suppose no $M$-augmenting path exists but $M$ is not maximum. Let $M^*$ be a bigger matching. Look at the symmetric difference $M \triangle M^*$ (edges in one but not both). Every vertex touches at most one $M$-edge and one $M^*$-edge, so each connected component is either:
• An alternating cycle (equal $M$ and $M^*$ edges — doesn't help), or
• An alternating path.

Since $|M^*| > |M|$, at least one path has more $M^*$-edges. That path starts and ends at vertices unmatched by $M$ — that's an augmenting path! Contradiction. $\square$

Necessity (easy direction):
If a matching pairs everyone in $X$, then for any subset $S \subseteq X$, those $|S|$ people are matched to $|S|$ distinct partners in $N(S)$. So $|N(S)| \ge |S|$. Done.

Sufficiency (hard direction — induction on $|X|$, two cases):
Assume $|N(S)| \ge |S|$ for every $S \subseteq X$.

Case 1 — "Lots of room everywhere":
Every proper nonempty $S \subset X$ has $|N(S)| \ge |S|+1$ (strict inequality).
Pick any $x \in X$, match it to any neighbor $y$. Remove $x$ and $y$ from the graph. The remaining graph still satisfies Hall (we had room to spare). By induction, match the rest. Add back $x$-$y$. Everyone matched!

Case 2 — "Some group is tight":
There exists $S \subset X$ with $|N(S)| = |S|$ exactly (no room to spare).
Match $S$ into $N(S)$ by induction (they form their own bipartite graph satisfying Hall).
Now match the leftovers $X_2 = X \setminus S$ into $Y_2 = Y \setminus N(S)$. Does Hall hold there?
For any $T \subseteq X_2$, apply Hall in the original graph to $T \cup S$:
$|N(T \cup S)| \ge |T \cup S| = |T| + |S|$. Subtract the $|S|$ neighbors already used: $|N(T) \cap Y_2| \ge |T|$.
So Hall holds in the leftover graph too. Induction matches $X_2$. Combine both matchings. $\square$

The translation:
• Left vertices = sets $S_1, \dots, S_k$
• Right vertices = all elements
• Edge $S_i$-$x$ iff $x \in S_i$
• SDR = matching that covers all left vertices
• For any index set $I$: $N(I) = \bigcup_{i \in I} S_i$

So Hall's condition $|N(I)| \ge |I|$ is exactly $|\bigcup_{i \in I} S_i| \ge |I|$.

SDR exists $\iff$ Hall's condition holds. One theorem, two languages. $\square$

Claim 1 proof:
Suppose $M_1 \neq M_2$ are both perfect matchings. In $M_1 \triangle M_2$, each vertex has degree exactly 0 or 2 (matched once in each), so every nontrivial component is a cycle. But trees are acyclic. Contradiction. $\square$

Claim 2 proof:
$n = 2k$ and $\delta(G) \ge k = n/2$. By Dirac's Theorem, $G$ has a Hamiltonian cycle. Since $n$ is even, take every other edge of that cycle:
$$v_1v_2,\; v_3v_4,\; \dots,\; v_{n-1}v_n$$ That's $n/2 = k$ disjoint edges covering all $n$ vertices. Perfect matching! $\square$

Easy direction: $\alpha'(G) \le \beta(G)$ always. Each matching edge needs a distinct cover vertex.

Hard direction — build a cover of size $|M|$:
Let $M$ be a maximum matching in bipartite $G = (X, Y)$.

Step 1: Let $U$ = vertices in $X$ not touched by $M$ (the unmatched ones).
Step 2: From $U$, explore all alternating paths (unmatched edge, matched edge, unmatched, matched...). Let $Z$ = all vertices reachable this way.
Step 3: Build the cover: $$C = \underbrace{(X \setminus Z)}_{\text{matched X not reachable}} \cup \underbrace{(Y \cap Z)}_{\text{reachable Y vertices}}$$ Why $C$ works:
• Every edge has at least one endpoint in $C$ (if not, we'd find an augmenting path, contradicting $M$ being maximum).
• Each matching edge puts exactly one vertex into $C$: either its $X$-endpoint (if not in $Z$) or its $Y$-endpoint (if in $Z$), never both.

So $|C| = |M|$, giving $\beta(G) \le \alpha'(G)$. Together: $\alpha'(G) = \beta(G)$. $\square$

Upper bound ($R(3,3) \le 6$) — the "pivot vertex" argument:
Pick vertex $v$ in $K_6$. It has 5 edges.
By pigeonhole: at least 3 have the same color (say red to $a,b,c$).
Look at the triangle $\{a,b,c\}$:
• Any red edge among them $\Rightarrow$ red triangle with $v$.
• All three blue $\Rightarrow$ blue triangle $\{a,b,c\}$.
Either way: monochromatic triangle!

Lower bound ($R(3,3) > 5$):
$K_5$: color a 5-cycle red, the remaining 5 edges (a pentagram) blue. Neither color has a triangle. So 5 vertices aren't enough.

Therefore $R(3,3) = 6$. $\square$

Lower bound ($R(3,4) > 8$):
An explicit coloring of $K_8$ exists with no red $K_3$ and no blue $K_4$. (You can construct one; not expected to memorize the exact edges.)

Upper bound ($R(3,4) \le 9$) — uses the improved recursion:
$$R(3,4) \le R(2,4) + R(3,3) - 1 = 4 + 6 - 1 = 9$$ The "$-1$" comes from Theorem 1.64* (parity trick), since $R(2,4) = 4$ and $R(3,3) = 6$ are both even.

Therefore $R(3,4) = 9$. $\square$

Let $N = R(p-1,q) + R(p,q-1)$. Pick any vertex $v$ in $K_N$. It has $N-1$ neighbors, colored red or blue.

$$|R| + |B| = N - 1 = R(p-1,q) + R(p,q-1) - 1$$ By pigeonhole, either $|R| \ge R(p-1,q)$ or $|B| \ge R(p,q-1)$.

If $|R| \ge R(p-1,q)$: Among the red neighbors, by definition of $R(p-1,q)$, there's either:
• A red $K_{p-1}$ $\Rightarrow$ add $v$ (connected to all of them by red) $\Rightarrow$ red $K_p$. Done!
• A blue $K_q$. Done!

If $|B| \ge R(p,q-1)$: Symmetric. Either red $K_p$ or blue $K_{q-1}$ plus $v$ gives blue $K_q$.

Every case gives a monochromatic clique. So $R(p,q) \le N$. $\square$

Suppose the bound is wrong: a "bad" coloring exists on $N = R(p-1,q) + R(p,q-1) - 1$ vertices (no red $K_p$, no blue $K_q$).

Then for every vertex $v$:
• Red-degree $< R(p-1,q)$ (otherwise red neighbors contain red $K_{p-1}$, giving red $K_p$ with $v$)
• Blue-degree $< R(p,q-1)$ (similarly)
• But red-deg + blue-deg $= N-1$, and the two upper bounds sum to exactly $N-1$.

So both must be equalities: every vertex has red-degree $= R(p-1,q)-1$.

Now the parity punch:
$R(p-1,q)$ is even, so $R(p-1,q)-1$ is odd.
Every vertex has odd red-degree. There are $N$ vertices, and $N$ is odd (even + even $- 1$).
So sum of red degrees = odd $\times$ odd = odd.
But degree sums are always even (handshake lemma)!

Contradiction $\Rightarrow$ no bad coloring exists $\Rightarrow$ $R(p,q) \le N$. $\square$

Proof (induction on $r+s$):

Base cases: $R(2,s) = s = \binom{s}{1}$ and $R(r,2) = r = \binom{r}{r-1}$.
(If you only need a red edge, you need $s$ vertices; if you only need a blue edge, you need $r$ vertices.)

Inductive step ($r,s \ge 3$): By Theorem 1.64:
$$R(r,s) \le R(r-1,s) + R(r,s-1)$$ Apply induction hypothesis to both:
$$\le \binom{r+s-3}{r-2} + \binom{r+s-3}{r-1} = \binom{r+s-2}{r-1}$$ The last step is just Pascal's identity: $\binom{n}{k-1} + \binom{n}{k} = \binom{n+1}{k}$. $\square$

Sanity check: $R(3,3) \le \binom{4}{2} = 6$. Matches the exact value!