Question 43
A convex $n$-gon is triangulated with triangulation $P$ of $n-3$ non-intersecting diagonals. An *independent set* of vertices is a set of vertices of $P$ where no two vertices are connected by a side or by a diagonal. Let $i(P)$ be the number of ways to choose an independent set of vertices with respect to the triangulation $P$. Prove that the minimum $i(P)$ is achieved for a zig-zag triangulation.