Lesson 249
Graph Theory
The math of what's possible
1:00The mathematical foundations of graphs — the laws that govern what structures are even possible before any algorithm is written.
By the end, you can
- State the handshaking lemma and use it to compute degree sums or edge counts.
- Explain why the number of odd-degree vertices in any graph must be even.
- Characterize a tree by its three equivalent definitions and compute its edge count.
- Distinguish an Euler circuit (polynomial to check) from a Hamiltonian cycle (NP-complete).
- Apply Euler's formula V − E + F = 2 to find the number of faces in a planar drawing.
- Use the edge bound E ≤ 3V − 6 to prove K5 is non-planar.
- State Kuratowski's theorem and identify the two forbidden graph minors.
- State Hall's marriage theorem and König's theorem and describe what each guarantees.
- Explain the Ramsey number R(3, 3) = 6 and articulate the broader principle of Ramsey theory.
Up next in Advanced Algorithms, Math & PL Theory
