Let G be a loop free graph connected graph, Prove if G is planar, then there exi

Q: Let G be a loop free graph connected graph, Prove if G is planar, then there exi

First we will prove that If G is a connected planar simple graph with e edges and v vertices, where v >=3, then e=3r => (2/3)e >=r using r =e-v+2 => e-v+2 e

ID: 2900397 • Letter: L

Question

Let G be a loop free graph connected graph, Prove if G is planar, then there exists a vertex (v) such that deg(v) < 6.

Hints *

Your help is greatly appreciated. Please show every step. Thanks for your time!!

Remember, the following equalties are true for all planar graphs: Euler's Formula: r - e + v = 2 2e = deg(Ri) 2e = deg(vi) (true for all graphs, not just planar graphs) This should be a proof by contradiction. What is the negation of the statement of the theorem? Please ask if you need help doing negations. If you do it correctly, you will likely use all three formulas at the top of the page. You can assume deg(Ri) ge 3 for all i. Note, it is incorrect to say K6 (or K5) is a subgraph! For example, if every vertex is at least degree 3, it does not follow that K$ is a subgraph. For instance, look at K3,3.

Explanation / Answer

First we will prove that

If G is a connected planar simple graph with e edges and v vertices, where v >=3, then

e<= 3v ? 6.

Proof :

A connected planar simple graph drawn in the plane divides the plane into regions,

say r of them. The degree of each region is at least three.

Note that the sum of the degrees of the regions is exactly twice the number of edges in

the graph, because each edge occurs on the boundary of a region exactly twice.

Because each region has degree greater than or equal to three, it follows that

2e = summation (i=1 to r ) deg(R_i) >=3r

=> (2/3)e >=r

using r =e-v+2

=> e-v+2<= (2/3)e => e<=3v-6

Now

Suppose G has one or two vertices, the result is true.

If G has at least three vertices, by the previous proof

we know that e<= 3v ? 6, => 2e <=6v ? 12.

If the degree of every vertex were at least six, then because

2e = summation (v in V) deg(v))

we would have 2e ? 6v.

But this contradicts the inequality 2e ? 6v ? 12.

It follows that there must be a vertex with degree no greater than five.

Navigate

Let G be a group. Prove that |Inn(G)|=1 if and only if G is abelian Solution con

Let G be a weighted undirected connected graph. Write, in pseudo-code, an algori

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

Let G be a loop free graph connected graph, Prove if G is planar, then there exi

Question

Explanation / Answer

Related Questions

Navigate