The Lumenary · Advanced undergraduate

Graph theory

Name: ______________________

Date: ______________________

You will learn to

Prove Hall's marriage theorem and apply it, including König's theorem and perfect matchings in regular bipartite graphs
Prove Euler's formula $V - E + F = 2$ for connected plane graphs and deduce that $K_5$ and $K_{3,3}$ are not planar; state Kuratowski's theorem
Prove the five colour theorem and state the four colour theorem accurately, including how it was proved
Prove Mantel's theorem and state Turán's theorem
Prove that $R(3, 3) = 6$ , the bound $R(s, t) \le \binom{s+t-2}{s-1}$ , and Erdős's lower bound $R(k, k) > 2^{k/2}$

1.
A graph has seven vertices with degrees $3, 3, 3, 3, 2, 2, 2$ . How many edges does it have?
2.
A connected plane graph has $10$ vertices and $15$ edges. How many faces does it have (counting the unbounded face)?
3.
What is the largest number of edges in a triangle-free graph on $7$ vertices?
4.
Which of these graphs are planar? (Select all that apply.)
- A. $K_4$
- B. $K_5$
- C. $K_{2,100}$
- D.The cube graph $Q_3$
- E.The Petersen graph
- F. $K_{3,3}$
5.
Corollary 5 says: a planar graph with $V$ vertices has $E \le 3V - 6$ . Which of the hypotheses are genuinely needed, in the sense that dropping one of them gives a counterexample? (Select all that apply.)
- A.The graph is simple (no parallel edges or loops).
- B. $V \ge 3$ .
- C.The graph is connected.
- D.Every vertex has degree at least $2$ .
6.
The proof that every red–blue colouring of $K_6$ has a monochromatic triangle starts: "a vertex $v$ has five edges, so three of them share a colour". If we try the same proof on $K_5$ , where does it break down?
- A.At the first step: $v$ has only four edges, which can split two red and two blue.
- B.At the last step: three vertices with no red edges among them need not form a blue triangle.
- C.The proof works for $K_5$ too, so $R(3, 3) \le 5$ .
- D.It breaks because $K_5$ is not planar.
7.
The Erdős–Szekeres bound says $R(s, t) \le \binom{s + t - 2}{s - 1}$ . What upper bound does it give for $R(4, 4)$ ?
8.
Edges of $K_6$ are unordered pairs s(a, b) : Sym2 (Fin 6), and a red–blue colouring is a function c : Sym2 (Fin 6) → Bool. Which Lean statement says that every colouring has a monochromatic triangle?
- A.∀ c : Sym2 (Fin 6) → Bool, ∃ a b d : Fin 6, a ≠ b ∧ b ≠ d ∧ a ≠ d ∧ c s(a, b) = c s(b, d) ∧ c s(b, d) = c s(a, d)
- B.∀ c : Sym2 (Fin 6) → Bool, ∃ a b d : Fin 6, c s(a, b) = c s(b, d) ∧ c s(b, d) = c s(a, d)
- C.∃ c : Sym2 (Fin 6) → Bool, ∃ a b d : Fin 6, a ≠ b ∧ b ≠ d ∧ a ≠ d ∧ c s(a, b) = c s(b, d) ∧ c s(b, d) = c s(a, d)
- D.∀ c : Sym2 (Fin 5) → Bool, ∃ a b d : Fin 5, a ≠ b ∧ b ≠ d ∧ a ≠ d ∧ c s(a, b) = c s(b, d) ∧ c s(b, d) = c s(a, d)
9.
A bipartite graph is given as a list adj, where adj[i] is the set of neighbours (in $B$ ) of vertex $i$ of $A$ . Write hall_violator(adj) that returns a smallest set $S \subseteq A$ , as a sorted tuple of indices, with $|N(S)| < |S|$ , or None if Hall's condition holds (so that, by Hall's theorem, a matching covering $A$ exists).
Computational — Practice

Answer key — Graph theory

1.
The degrees add up to $4 \cdot 3 + 3 \cdot 2 = 18 = 2|E|$ , so $|E| = 9$ .
2.
$F = 2 - V + E = 2 - 10 + 15 = 7$ . (The Petersen graph also has $10$ vertices and $15$ edges — but it is not planar, so it has no plane drawing to which this applies.)
3.
By Mantel's theorem a triangle-free graph on $7$ vertices has at most $\lfloor 49/4 \rfloor = 12$ edges, and $K_{3,4}$ is triangle-free with exactly $3 \cdot 4 = 12$ edges. So the answer is $12$ .
4.
$K_4$ , $K_{2,100}$ and $Q_3$ are planar. $K_5$ ( $10 > 9$ ) and $K_{3,3}$ ( $9 > 8$ ) violate the edge bounds from Euler's formula. The Petersen graph satisfies both simple bounds, but it has girth $5$ , so every face would have length at least $5$ : $5F \le 2E = 30$ gives $F \le 6$ , while Euler's formula would need $F = 2 - 10 + 15 = 7$ . So it is not planar either.
5.
Simplicity and $V \ge 3$ are needed: a bundle of parallel edges, or the single edge $K_2$ , breaks the inequality. Both are used in the step "every face has length at least $3$ ". Connectedness is a convenience of the proof, not a hypothesis of the result, and minimum degree plays no role.
6.
In $K_5$ each vertex has only $4$ edges, and $4$ edges can be split $2 + 2$ between the colours, so the pigeonhole step fails. The pentagon colouring realises exactly this at every vertex, and it has no monochromatic triangle.
7.
$\binom{4 + 4 - 2}{4 - 1} = \binom{6}{3} = 20$ . The recursion gives the same: $R(3, 4) \le R(2, 4) + R(3, 3) = 10$ , so $R(4, 4) \le 2 \cdot 10 = 20$ . (Using the exact value $R(3, 4) = 9$ gives $18$ , which is the truth.)
8.
Option a. Option b drops distinctness and becomes trivial; option c has the wrong quantifier on the colouring; option d is the false statement for $K_5$ , refuted by the pentagon colouring. Writing a formal statement forces exactly these decisions — which is one of the benefits of formalisation.
9.
```
from itertools import combinations

def hall_violator(adj):
    for size in range(1, len(adj) + 1):
        for S in combinations(range(len(adj)), size):
            N = set().union(*(adj[i] for i in S))
            if len(N) < len(S):
                return S
    return None
```
This checks all $2^{|A|}$ subsets, so it takes exponential time. Hall's theorem guarantees that a violator exists exactly when no matching covers $A$ — and augmenting paths decide that in polynomial time, which is why in practice one searches for the matching, and extracts a violator from the failed search when there is none.