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.
, 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.
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.
May 2017
April 2017