Question: (Donated by David Cox) Consider any convex polygon with at least four sides and decompose it into triangles by connecting vertices. (Do not let chords cross or create new vertices.) See Figure for an example of this process.
(a) Show that no matter how you decompose the polygon into triangles, at least two of the triangles have two sides (each) in common with the original polygon.
(b) For any decomposition of a convex polygon into triangles, create a graph as follows. Place a vertex in each triangle and join two vertices when their two surrounding triangles share an edge.
(i) What kind of graph is this? (Feel free to justify your answer.)
(ii) Does every graph of this type arise from some convex polygon? Explain.
(iii) What aspect of the graph corresponds to a triangle that has two edges in common with the original polygon?
(iv) What theorem about graphs did you prove in the previous part of this problem?
