1
$\begingroup$

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?

3 Answers 3

2

Hint: how many faces are there? Then each one has a minimum of three edges in its boundary.

1

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

http://www.scribd.com/doc/101341419/Course-Notes

0

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.