Solution to An orientation of a graph G = (V,E) is any directed graph G'= (V,E) arising … - Sikademy
Author Image

Archangel Macsika

An orientation of a graph G = (V,E) is any directed graph G'= (V,E) arising by replacing each edge {u, v} belonging to 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. (proof by induction)

The Answer to the Question
is below this banner.

Can't find a solution anywhere?

NEED A FAST ANSWER TO ANY QUESTION OR ASSIGNMENT?

Get the Answers Now!

You will get a detailed answer to your question or assignment in the shortest time possible.

Here's the Solution to this Question

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

Related Answers

Was this answer helpful?

Join our Community to stay in the know

Get updates for similar and other helpful Answers

Question ID: mtid-5-stid-8-sqid-3433-qpid-2132