Question

If every region of simple planar graph (with n vertices and e edges) embedded in a plane is bounded by k edges show that. e=k(n-2)/k-2​

Answer 1

Answer:

K5: K5 has 5 vertices and 10 edges, and thus by Lemma 2 it is not planar. K3,3: K3,3 has 6 vertices and 9 edges, and so we cannot apply Lemma 2. But notice that it is bipartite, and thus it has no cycles of length 3. ... In fact, any graph which contains a “topological embedding” of a nonplanar graph is non- planar.