Problem of the Week #126 - August 25th, 2014

[Chris L T521]

Here's this week's problem!

-----

Problem: Show that in any simple, connected, planar graph, $e\leq 3v-6$ (i.e. the number of edges is less than or equal to six less than three times the number of vertices).

-----Remember to read the http://www.mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to http://www.mathhelpboards.com/forms.php?do=form&fid=2!

 

[Chris L T521]

This week's problem was correctly answered by magneto. You can find his solution below.

[sp]Given a simple, connected, planar graph $G$. We call a degree of a face, $d(f)$, the number of edges that touch the face $f$.
We know that each edge touches exactly two faces, so $2e = \sum_f d(f)$. We also know that $d(f) \geq 3$, i.e., each face
is bounded by at least 3 edges (a triangle), else we have parallel edges or loops, which violates the fact $G$ is simple.
Hence, we have $2e = \sum_f d(f) \geq 3f$.

Euler's formula on planar graph states $v - e + f = 2$, or $6 = 3v - 3e + 3f \leq 3v - 3e + 2e = 3v - e$.
Hence, $e \leq 3v - 6$.[/sp]