13.4 Exercises

Merging two adjacent vertices of a planar graph yields another planar graph.

Any embedding of a planar graph will have the same number of faces.

Show that any connected triangle-free planar graph has at least one vertex of degree three or less. Prove by induction on the number of vertices that any connected triangle-free planar graph is 4-colorable.

Show that every planar graph with at least 4 vertices has at least 4 vertices of degree less than or equal to 5. (Hint : Consider a maximal planar graph.)

Let $G$ be a plane graph and $G^{\ast }$ be its dual. Prove the following :

• •

  $G^{\ast }$ is connected.

• •

  If $G$ is connected, then each face of $G^{\ast }$ contains exactly one vertex of $G$.

• •

  ${(G^{\ast })}^{\ast }=G$ iff $G$ is connected.

Prove that a set of edges $T\subset E(G)$ in a connected plane graph form a spanning tree iff the duals of the edges $E(G)-T$ form a spanning tree of $G^{\ast }$.

Prove that every $n$-vertex self-dual plane graph has $2n-2$ edges. For all $n\ge 4$, construct a simple $n$-vertex self-dual plane graph.