Planarity MCQ Quiz in বাংলা - Objective Question with Answer for Planarity - বিনামূল্যে ডাউনলোড করুন [PDF]
Last updated on Apr 4, 2025
Latest Planarity MCQ Objective Questions
Top Planarity MCQ Objective Questions
Planarity Question 1:
Let δ denote the minimum degree of a vertex in a graph. For all planar graphs on n vertices with δ ≥ 3, which one of the following is TRUE?
Answer (Detailed Solution Below)
Planarity Question 1 Detailed Solution
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) =
Option 1 is the correct answer.
Planarity Question 2:
The maximum number of edges in a simple graph with 7 vertices and 3 components is _____.
Answer (Detailed Solution Below) 10
Planarity Question 2 Detailed Solution
Data:
number of vertices = n = 7
number of components = k = 3
Formula:
Solution:
Planarity Question 3:
The chromatic number of a planar graph is not greater than __________
Answer (Detailed Solution Below)
Planarity Question 3 Detailed Solution
The chromatic number of a planar graph is no greater than 4. (The Four Colour Theorem)
Planarity Question 4:
A Graph G is a connected planar simple graph with ‘e’ edges and ‘v’ vertices, with v > 3 , if all cycles in G have length > 4 then which of the following relations always hold?
Answer (Detailed Solution Below)
Planarity Question 4 Detailed Solution
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
Planarity Question 5:
Maximum number of edges in a triangle free, simple planar graph of 10 vertices is:
Answer (Detailed Solution Below) 16
Planarity Question 5 Detailed Solution
e ≤ 2v − 4 if simple planar graph has no cycles of length 3.
Planarity Question 6:
Graph G (V, E) is connected planar with no cycles of length less than 4,
if |V| = 15 then maximum value of |E| is:
Answer (Detailed Solution Below) 26
Planarity Question 6 Detailed Solution
For connected planar graphs with no cycles of length 3.
|E| ≤ 2 |V| - 4
otherwise
|E| ≤ 3 |V| - 6
for all connected planar graphs.