Dear SSD, please work on graph theory
by cjquines0, Nov 28, 2016, 12:40 PM
own? wrote:
Prove that, for all
, we can find a maximal planar graph† with diameter‡ 2 that has
vertices.
†A planar graph is one that can be drawn in such a way that its edges intersect only at their endpoints. A maximal planar graph is a planar graph such that adding any edge would make it non-planar.
‡The diameter of a graph is the largest distance between any two of its vertices.


†A planar graph is one that can be drawn in such a way that its edges intersect only at their endpoints. A maximal planar graph is a planar graph such that adding any edge would make it non-planar.
‡The diameter of a graph is the largest distance between any two of its vertices.
Solution
Note that a maximal planar graph is a triangulation of the plane: all the faces, including its outer one, are bounded by three edges. If a face was bounded by more than three edges, we can draw an edge connecting a diagonal of that face, making a planar graph with one more edge.
Now consider a regular polygon with
vertices and triangulate it. Add another vertex and connect it to each of the vertices of the original polygon. This produces a maximal planar graph. The distance between any two vertices of the polygon is 2 because of the outer vertex, and the distance between the outer vertex and any vertex in the polygon is 1, so this graph has diameter 2.
Now consider a regular polygon with

Tidbit
ssd, please start working on graph theory again. We need a research project. Thunk.