Planarity MCQ Quiz in తెలుగు - Objective Question with Answer for Planarity - ముఫ్త్ [PDF] డౌన్‌లోడ్ కరెన్

Concept:

• Euler’s formula for connected graph = n – e + f = 2
• Planar graph with minimum degree 3 for each vertex we can say that 3n ≤ 2e

Calculation:

n – e + f = 2 = (e = n + f – 2), put value of e in 3n ≤ 2e

After putting: 3n ≤ 2 (n + f - 2) = \(\frac{{3n}}{2} \le n + f - 2 = f \ge \frac{{3n}}{2} - n + 2 = f \ge \frac{n}{2} + 2\)

Option 1 is the correct answer.

Data:

number of vertices = n = 7

number of components = k = 3

Formula:

\({{\rm{E}}_{{\rm{max}}}} = \frac{{\left( {{\rm{n}} - {\rm{k}}} \right)\left( {{\rm{n}} - {\rm{k}} + 1} \right)}}{2}\)

Solution:

\({{\rm{E}}_{{\rm{max}}}} = \frac{{\left( {7 - 3} \right)\left( {7 - 3 + 1} \right)}}{2}\;\)

\({{\rm{E}}_{{\rm{max}}}} = {\rm{\;}}10{\rm{\;\;}}\)

The chromatic number of a planar graph is no greater than 4. (The Four Colour Theorem)

The sum of the degrees of the regions is equal to twice the number of edges. But each region must degree > 4 because all cycles have length > 4. So we have 2e > 4 r

By Euler’s formula: v – e + r = 2, so combining these

e – v + 2 <  e ⇒  e < 2v – 4

For connected planar graphs with no cycles of length 3.

|E| ≤ 2 |V| - 4

otherwise

|E| ≤ 3 |V| - 6