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)33Trivial
4 (quadrilateral)55Esther Klein
5 (pentagon)99Endre Makai (credited in the 1935 paper); later published proof by Kalbfleisch, Kalbfleisch and Stanton (1970)
6 (hexagon)1717Szekeres and Peters (2006, computer search)
7 and upUnknown33, 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.

Happy Ending Problem – Numberphile (Numberphile). The story of Klein, Szekeres and Erdős, with drawings.
An extra little bit for the Happy Ending Problem (Numberphile2). More detail on the 5-point argument.
Andrew Suk: Old and new developments on the Erdos-Szekeres convex polygon problem (BIMSA). A research talk from the mathematician who proved the near-optimal bound.

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.

1. How many points (no three on a line) guarantee a convex quadrilateral?
Found a bug? Let us know!
2. What does the Erdős–Szekeres conjecture predict for a convex hexagon?
Found a bug? Let us know!
3. Why is it called the happy ending problem?
Found a bug? Let us know!
4. What did Andrew Suk prove in 2016?
Found a bug? Let us know!
5. How many points guarantee an empty convex hexagon?
Found a bug? Let us know!

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

Sources and Further Reading

Related to This Article

What people say about "Happy Ending Problem Explained: The 5-Point Proof - Effortless Math"?

No one replied yet.

Leave a Reply