Prove that no set of $n$ points can be triangulated in more than $2^{n \choose 2}$ ways.

Question

Prove that no set of $n$ points can be triangulated in more than $2^{n \choose 2}$ ways.

So I am really confused about the argument. We have two choices to triangulate 4 sided polygon.

So the natural upper bound would be $2^{n \choose 4}$. I am not sure why we can reduce it to choosing only 2 points, instead of 4...

Problem is from Computational Geometry De Berg.

Answer 1

We have ${n \choose 2}$ pairs of vertices and for each pair we can connect or not connect thus we have $2^{n \choose 2}$ ways to connect.