Answer to Question #152979 in Discrete Mathematics for Miry

Question #152979
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)
1
Expert's answer
2020-12-29T15:07:13-0500

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"


Need a fast expert's response?

Submit order

and get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS!

Comments

No comments. Be the first!

Leave a comment

LATEST TUTORIALS
New on Blog
APPROVED BY CLIENTS