A graph is planar if it can be drawn in such a way that edges do not cross.
Prove that the following three graphs are planar.
The complete graph \(K_5\) with \(5\) vertices is not planar. You can try as much as you want but you can‘t manage to draw that graph without intersecting edges. Similarly, the complete bipartite graph \(K_{3,3}\) is not planar. We will later use Euler's theorem to prove that these two graphs are not planar.
A face of a planar graph is a connected region in the plane bounded by the edges of the graph.
How many faces does the following graph have?
A triangulation of a planar graph consists of adding edges to the graph until every face is a triangle.
Determine a triangulation of the graph from problem 2.
The proof is on page 241 of the textbook.
We can now prove that \(K_5\) cannot be planar. The number of vertices of \(K_5\) is \(n=5\). The number of edges is \(e=10\). Let us assume that \(K_5\) is planar. Then it must have faces. Let us denote by \(f\) the number of faces. Let us denote by \(e_1\), \(e_2\), \(\dots\), \(e_f\) the number of edges on the faces. Observe that \[e_1+e_2+\cdots+e_f=2e.\] The last equality is proved in similar way as the handshake theorem: when we add the edges for all the faces and create the sum \(e_1+e_2+\cdots+e_f\) then each edge is counted exactly twice because each edge belongs to exactly two faces. Since each face has at least three edges we have \(e_1+e_2+\cdots+e_f\geq 3f\). Therefore \(2e\geq 3f\). From Euler's formula we obtain \[e+2=n+f\leq n+\frac23e.\] The inequality \(n+\frac23e\geq e+2\) is equivalent to \(n\geq \frac e3+2\) which is the same as \(3n\geq e+6\). This is not possible because for \(n=5\) and \(e=10\) we have \(3n=15\) while \(e+6=16\) and \(15\geq 16\) is just wrong. This is a contradiction.
The proof that \(K_{3,3}\) is not planar is similar. If a graph is triangle-free then the inequality \(3n\geq e+6\) can be improved to \(2n\geq e+4\). Since the graph \(K_{3,3}\) is bipartite, and hence triangle-free, the \(2n\geq e+4\). However, for \(K_{3,3}\) we have \(n=6\) and \(e=9\). The number \(2n\) is equal to \(12\), while \(e+4\) is equal to \(13\) and \(12\geq 13\) is a contradiction.
A polyhedron is a solid object in 3 dimensions. Every convex polyhedron corresponds to a planar graph. We can see that in the following way: First we blow the air in the polyhedron until it becomes a sphere.
Then we find a point \(P\) on the sphere that is not an edge or a vertex of the polyhedron. We then rotate our point of view so that \(P\) is the top of the sphere, or north pole for those of you familiar with geography. We then find one plane far away below the south pole. Then we find intersections of this plane with all lines connecting \(P\) with points of the polyhedron. The obtained projection is a planar graph.
Prove that at least one face of a convex polyhedron has fewer than or equal to \(5\) edges.