Question

 An orientation of a graph G = (V, E) is any directed graph G0 = (V, E0 ) arising by replacing each edge {u, v} ∈ E by the directed edge (u, v) or by the directed edge (v, u). Show that for every planar graph there is an orientation such that each vertex has at most five outgoing edges.

Answer 1

Let v is number of vertices, e is number of edges.

If every vertex had degree at least 6, then the sum of the vertex degrees is at least 6v. But since the sum of the vertex degrees equals 2e , by the Handshake Lemma, we have $e\geq 3v$ contradicting the fact that $e\leq3v-6$ (by Theorem).

The Theorem:

Suppose a connected planar graph has $v\geq3$ vertices and $e$ edges.

Then

$e\leq3v-6$

Proof. By definition, a connected graph is planar iff it has a planar embedding. So

suppose a connected graph with v vertices and e edges has a planar embedding

with f faces. Every edge is traversed exactly twice by the face boundaries. So the sum of the lengths of the face boundaries is exactly 2e. Also, when $v\geq3$ , each face boundary is of length at least three, so this sum is at least 3f . This implies that

$3f\leq2e$

But $f=e-v+2$ by Euler’s formula, and substituting gives

$3(e-v+2)\leq2e$

$e-3v+6\leq0$

$e\leq3v-6$