this is a discrete math question 2. Answer the following questions, justify your

Question

this is a discrete math question

2. Answer the following questions, justify your answer: 10 pts (a) What is the largest value of n for which the complete graph Kn is planar? (b) What is the largest value of n for which the complete bipartite graph Ko, is planar? c)How many vertices are there in a connected planar simple graph with 12 regions and 20 edges? (d) Let G be a connected planar graph with 21 vertices. What is the maximum num ber of edges that G can have? (e) What is the chromaticmber for Cesa, K3ndK7

Explanation / Answer

a) The largest value of n for which a complete graph is planar is 4 i.e K4 is planar.

b) The largest value of n is 2 such that K6,2 is planar.

c) According to eulers formula V-E+R = 2

Here E= 20 and R=12

Therefore V= 20 + 2 - 12 = 22 -12 = 10

d) We know in planar graphs E>=3/2F....(i)

by eulers formula F = 2 - V + E

or F = 2 - 21 + E

or F = E - 19

Substituting F in (i) we get:-

E >= 3/2(E - 19)

or, E>= 3/2E - 57/2

or, 1/2E<=57/2

or, E<=57

Therefore maximmum number of edges is 57

e) C654 has chromatic number 2 as even length cycle.

K32,34 has chromatic number 34 as max(32,34) = 34

K67 has chromatic number 67 as complete graph.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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