Happy Ending Problem Explained: The 5-Point Proof
Quick answer: The happy ending problem asks how many points in the plane, with no three on a line, guarantee n points forming a convex polygon. Esther Klein showed 5 points always contain a convex quadrilateral. Erdős and Szekeres (1935) conjectured the answer is 2^(n−2) + 1; it is proved for n = 4, 5 and 6 (17 points). In 2016, Andrew Suk proved it is correct up to lower-order terms. The name comes from Klein and Szekeres, who married in 1937.
Put five dots on a page, with no three in a straight line. Then, however you placed them, four of them always form a convex quadrilateral, a four-sided shape with no dents. This little observation by Esther Klein in Budapest in the early 1930s started a problem that is still open, and a marriage. Paul Erdős named it the happy ending problem because Klein and George Szekeres, who worked on it together, married in 1937.
Two words to know: a polygon is convex if it has no dents (every corner points outward), and points are in general position if no three lie on one line. No other special arrangement is required.
Why 5 Points Always Work
Look at the convex hull of the 5 points, the shape you get by stretching a rubber band around them.
- If the hull has 5 or 4 corners, any 4 of those corners form a convex quadrilateral.
- If the hull is a triangle, the other 2 points are inside it. Draw the line through those 2 points. It splits the plane in two, so by the pigeonhole principle two of the triangle’s three corners lie on the same side of that line. Those two corners and the two inside points form a convex quadrilateral: the two inside points lie on one side of the line through them and the two corners on the same side, so none of the four sits inside the triangle formed by the other three.
Four points are not enough: place three at the corners of a triangle and one inside, and no convex quadrilateral exists.
The Erdős–Szekeres Conjecture
Let \(N(n)\) be the smallest number of points (no three on a line) that always contains \(n\) points in convex position. Erdős and Szekeres proved in 1935 that \(N(n)\) exists, using an early form of Ramsey theory, and conjectured an exact formula:
\[ N(n) = 2^{n-2} + 1. \]
In 1961 they constructed sets of \(2^{n-2}\) points with no convex \(n\)-gon, so the formula, if true, cannot be improved.
| Convex polygon \(n\) | Points needed \(N(n)\) | Formula \(2^{n-2} + 1\) | Proved by |
|---|---|---|---|
| 3 (triangle) | 3 | 3 | Trivial |
| 4 (quadrilateral) | 5 | 5 | Esther Klein |
| 5 (pentagon) | 9 | 9 | Endre Makai (credited in the 1935 paper); later published proof by Kalbfleisch, Kalbfleisch and Stanton (1970) |
| 6 (hexagon) | 17 | 17 | Szekeres and Peters (2006, computer search) |
| 7 and up | Unknown | 33, 65, … | Open |
How Close Are We?
The 1935 upper bound was about \(4^n\), far above \(2^n\). For 80 years, improvements were small. Then in 2016, Andrew Suk proved
\[ N(n) \le 2^{\,n + o(n)}, \]
(a 2016 preprint, published in 2017), which matches the conjectured \(2^{n-2}\) up to lower-order terms in the exponent. In 2020, Andreas Holmsen, Hossein Nassajian Mojarrad, János Pach and Gábor Tardos sharpened this to \(2^{\,n + O(\sqrt{n \log n})}\). In 2026, Sujin Baek and Martin Balko published progress on a relaxed version and on special point sets. The exact formula is still unproved; Erdős offered 500 dollars for a proof.
Empty Polygons: A Cousin Solved by Computer
Erdős also asked about empty convex polygons, with no other points inside. Every 10 points contain an empty convex pentagon, but there are arbitrarily large sets with no empty heptagon (Horton, 1983). For empty hexagons, a 29-point set with none was already known; in 2024, Marijn Heule and Manfred Scheucher used a SAT solver to prove that every set of 30 points contains one. A separate 2024 team (Subercaseaux, Nawrocki, Gallicchio, Codel, Carneiro and Heule) verified the result in Lean.
Common Misconceptions
“It needs the points in special positions.” No special arrangement is required, apart from no three points on a line.
“It is solved because Suk proved it.” Suk proved it asymptotically. The exact value \(2^{n-2} + 1\) is open for every \(n \ge 7\).
Watch: The Happy Ending Problem in Video
If you learn better by watching, these videos are worth your time.
Check Your Understanding
Five quick questions to see how much of this has stuck. Pick an answer and press Submit; you will see a short explanation either way.
Answer each question and press Submit to see your result right away.
Frequently Asked Questions
What is the happy ending problem?
It asks how many points in the plane, with no three on a line, guarantee that some n of them form a convex polygon. For a quadrilateral the answer is 5.
Why is it called the happy ending problem?
Paul Erdős named it after Esther Klein and George Szekeres, who worked on it together and married in 1937.
Has the happy ending problem been solved?
Not fully. The conjecture N(n) = 2^(n−2) + 1 is proved for n up to 6. Andrew Suk proved it holds up to lower-order terms (2016 preprint, 2017 paper), but the exact formula is open for n ≥ 7.
How many points guarantee a convex pentagon?
Nine points, with no three on a line, always contain a convex pentagon, and 8 points can avoid one.
Keep Exploring
- Ramsey Numbers Explained: The Party Problem and R(5,5)
- Erdős Problems Explained: What AI Has Actually Solved
- Erdős Unit Distance Problem: What AI Disproved
Sources and Further Reading
Related to This Article
More math articles
- How to Master the Average Rate of Change
- Stem –and–Leaf Plots
- The Best Grade 3 Math Book for Colorado Students
- ASWB First vs Next Questions: Read the Decision the Item Asks For (2027 Prep)
- Free Grade 8 English Worksheets for Florida Students
- Texas STAAR Algebra 1 Free Worksheets: 59 Printable TEKS-Aligned Algebra 1 PDFs with Answer Keys
- How Is the CLEP College Algebra Test Scored?
- 10 Most Common 7th Grade Georgia Milestones Assessment System Math Questions
- Statistics and Probability Flashcards
- 5 Best Touchscreen Monitors for Teaching Online


What people say about "Happy Ending Problem Explained: The 5-Point Proof - Effortless Math"?
No one replied yet.