TransWikia.com

Show that the number of faces in a planar connected graph on $n$ vertices is bounded from above by $2n-4$

Mathematics Asked by Carl J. on February 1, 2021

Let $G$ be a planar (and connected) graph on $n geq 3$ vertices. Show that the number of faces of $G$ is bounded from above by $2n-4$.

Can someone help me with an idea on this problem?

One Answer

It is well known that the number of edges is at most $3n-6$ in a planar graph on $n$ vertices. This can be easily proven using the following idea: Take a planar graph $G$ and take an arbitrary face which is not a triangle. We quickly realize that we can always add diagonal edges in each non-triangular face without destroying planarity until we have contructed a plane triangulation. Using Euler's formula, given by $n-m+f=2$, whereby $n$ is the number of vertices, $m$ is the number of edges and $f$ is the number of faces, the above bound is quickly found.

Corollary: A planar graph $G$ with $n geq 3$ vertices has at most $3n-6$ edges.

Proof: Assume that $G$ is a maximal planar graph, that is a planar graph for which we cannot add any more edges without destroying planarity. By Euler's formula: $n-m+f=2$. Each face must be a triangle by maximality of $G$ (or we could add diagonals). Since every edge bounds two faces, $2m=3f implies n-m+ frac{2}{3}m=n-frac{1}{3}m=2 iff m=3n-6$.

Now, use Euler's formula again and plug in the above results.

$n - m +f leq 2\ n-3n+6 +f leq 2 \ f leq 2n -4$

Hence the number of faces in a planar graph is at most $2n -4$.

Answered by David Scholz on February 1, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP