A simple connected planar graph with $6$ vertices and $12$ edges. How do we show that each of the face is bounded by three edges?
Simple connected planar graph with $6$ vertex and $12$ edges , each of the face is bdd
3 Answers
Hint: how many faces are there? Then each one has a minimum of three edges in its boundary.
You should have learned about Euler's formula
$p-q+f=2$ $p$ - vertices $q$ - edges $f$ - faces
You can use that result to show each face has 3 edges, look at 7.4.2
Since $G$ is planar we can use Euler's Identity, $n-m+r=2$, where $n=6$ and $m=12$. Thus $6-12+r=2$ implies that $r=8$. By The First Theorem of Graph Theory the sum of all the degrees in $G$ is $2m=2(12)=24$. Since the number of regions is $r=8$ we know that each region is bounded by $24/8=3$ edges.
If $G$ is a connected plane graph with at least three edges, then the boundary of every region of $G$ has at least three edges. In this particular problem it turns out that the boundary of every region of $G$ has three edges.