Day 7 — Graph Theory
Time: ~45 min · Topic: graph theory
The problem
The complete graph K_7 has an edge connecting every pair of its 7 vertices. What is the minimum number of edges that must be removed to make K_7 planar (drawable in the plane with no crossing edges)?
Hint: Think about what Euler's Formula for planar graphs tells you about the maximum number of edges a planar graph can have.
Try it yourself
Take a few minutes. Don't peek at the steps. If you get stuck, the hint above is enough to nudge you forward.
Step-by-step solution
- Count the edges in K_7. A complete graph on n vertices has C(n, 2) = n(n-1)/2 edges. So K_7 has 7(6)/2 = 21 edges.
- Recall Euler's Formula for connected planar graphs: v - e + f = 2, where v = vertices, e = edges, f = faces. A key consequence is the inequality e <= 3v - 6.
- Apply the upper bound. For v = 7: e <= 3(7) - 6 = 15. So any planar graph on 7 vertices can have at most 15 edges.
- Find the minimum removals. K_7 has 21 edges but a planar graph on 7 vertices allows at most 15. Therefore, at least 21 - 15 = 6 edges must be removed. Since a maximal planar graph (triangulation) on 7 vertices with exactly 15 edges exists, this bound is achievable.
Answer: At least 6 edges must be removed from K_7 to make it planar.
Why this matters
Euler's Formula (v - e + f = 2) was discovered in 1758 and is considered the first theorem of topology — it even applies to any convex polyhedron you can hold in your hand!
This day in math: The King of Invariant Theory Is Born
April 27, 1837 · Paul Gordan
On April 27, 1837, German mathematician Paul Gordan was born in Breslau. Known as "The King of Invariant Theory," Gordan proved that the ring of invariants of binary forms is finitely generated — a landmark result in algebra. He also mentored Emmy Noether, one of the greatest mathematicians of all time, supervising her doctoral thesis at the University of Erlangen in 1907.
Why it matters: Gordan's work laid the foundation for modern abstract algebra, and his famous clash with Hilbert over constructive vs. existential proofs shaped how mathematicians think about what counts as a valid proof to this day. His mentorship of Emmy Noether helped launch a revolution in algebra and physics.
Did you know?
Zero factorial (0!) equals exactly 1 — not zero. This means that the number of ways to arrange absolutely nothing is precisely one way: do nothing at all. It's one of the most counterintuitive results in all of mathematics, and it's essential for countless formulas to work correctly.
Factorial means multiplying all positive integers down to 1, so 3! = 3 x 2 x 1 = 6. But there's a beautiful pattern: 4! = 24, 3! = 24/4 = 6, 2! = 6/3 = 2, 1! = 2/2 = 1... and following that same logic, 0! = 1/1 = 1. Defining 0! = 1 also makes the binomial coefficient and combinations formulas work perfectly — without it, expressions like "choose 0 items from n" would break. It's not just a convention; the math demands it.
Done?
- Solved the problem (or read through the steps)
- Read the history note
- Read the "did you know" fact