Given a simple polygon of $n$ vertices, and $n$ sufficiently large, prove that there exists a diagonal that splits the polygon into two polygons, each with at most ${3n\over 4}$ vertices?
So I know this:
It's a direct relation of the 4 color theorem. Take a planar graph G, and color it in 4 colors. All vertices except the ones in the color class of greatest size form a vertex cover consisting of at most 3*V(G)/4 vertices.
It's 3/4*n because we are working with triangulation.
So my question is this: What else do I need to prove this by induction? And where would you start to prove this?