A maximal plane graph is a plane graph G = (V, E) with n ? 3vertices such that if we join any two non-adjacent vertices in G,we obtain a non-plane graph.
a) Draw a maximal plane graphs on six vertices.
b) Show that a maximal plane graph on n points has 3n ? 6 edgesand 2n ? 4 faces.
c) A triangulation of an n-gon is a plane graph whose infiniteface boundary is a convex n-gon and all of whose other faces aretriangles. How many edges does a triangulation of an n-gonhave?
