A graph is said to be planar if it can be drawn on a plane so that no two edges intersect except at the end vertices of the edges.
Let us consider the drawing of a planar graph on a plane.
By letting be the number of faces (i.e., closed regions including exterior one) in the drawing of a connected planar graph with vertices and edges, it holds , which is called the Euler's formula in the graph theory.
(1) Give a planar drawing of graph shown in Figure 1, and show that the drawing fulfills the Euler's formula.
(2) Complement of simple graph , denoted as , is a graph with vertex set and edge set . Give a planar drawing of the complement of graph .
(3) There is an upper limit on the number of edges so that a simple graph is planar. Prove that any simple planar graph with vertices and edges satisfies .
(4) With inequality , prove that for any simple graph with at least 11 vertices, or is not planar.
Suppose a connected graph with vertices and edges has a planar embedding with faces.
Since every edge is traversed exactly twice by the face boundaries, the sum of the lengths of the face boundaries is exactly .
Also, each face boundary is of length at least , so this sum is at least .
This implies that
But by Euler’s formula, and substituting into the above gives
