Assume that a graph $G$ is a loop-free, connected planar graph with $e > 2$.

Show that $3r \le 2e$ and $e \le 3v - 6$


1 Answer 1


When G is not a multigraph, each region would have at least 3 edges, therefore a degree of $\ge$ 3.

Also note that 2e = |E|, which is sum of degrees of r regions, where 2e $\ge$ 3r.

Using Euler's theorem, 2 = v - e +r $\le$ v - e + (2/3)e = v - (1/3)e.

Then, we have:

6 $\le$ 3v - e

If we move 6 and e around, we get e $\le$ 3v - 6.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .