Previous Year Questions: Planar Graph | Engineering Mathematics for Computer Science Engineering - Computer Science Engineering (CSE) PDF Download

Q1: In an undirected connected planar graph G, there are eight vertices and five faces. The number of edges in G is _________.  (2021 SET-1)
(a) 15
(b) 13
(c) 11
(d) 10
Ans: (c)
Sol: Given: For a planner graph G 

• Number of vertices (V) = 8
• Number of region/faces (R/f) = 5
• Number of edges (E) = ?

For any planner graph V + F = E + 2

⇒ 8 + 5 = E + 2
⇒ E = 13 − 2 = 11
∴ Number of edges in given graph G is 11.

Q2: 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?  (2014 SET-3)
(a) In any planar embedding, the number of faces is at least (n/2) + 2
(b) In any planar embedding, the number of faces is less than (n/2) + 2
(c) There is a planar embedding in which the number of faces is less than (n/2) + 2
(d) There is a planar embedding in which the number of faces is at most (n/δ+1)
Ans: (a)
Sol: If δ is the minimum degree, given as 3.
Take a vertex of degree 3. This vertex has 3 edges incident to it.
These 3 edges further lead to 3 more vertices. Now these vertices can have a minimum degree of 3.
We get the following planar graph.

This is the planar graph with minimum degree 3 for each vertex.
From this graph, we can say that 3n ≤ 2e → (1)
As per Euler's formla : n − e + f = 2 ⇒ e = n + f − 2 →(2)
From (1) and (2)
n + f − 2 ≥ (3n/2)
⇒ f ≥ (3n/2) - n + 2
⇒ f ≥ (n/2) + 2 (No of faces is at least ((n/2) + 2).

Q3: Let G be a simple undirected planar graph on 10 vertices with 15 edges. If G is a connected graph, then the number of bounded faces in any embedding of G on the plane is equal to  (2012)
(a) 3
(b) 4
(c) 5
(d) 6
Ans: (d)
Sol: For any planar graph,
n(no. of vertices) - e(no. of edges) + f(no. of faces) = 2
f = 15 − 10 + 2 = 7
number of bounded faces = no. of faces -1
= 7 − 1 = 6
So, the correct answer would be D.

Q4: K4 and Q3 are graphs with the following structures
Which one of the following statements is TRUE in relation to these graphs?  (2011)
(a) K4 is planar while Q3 is not
(b) Both K4 and Q3 are planar
(c) Q3 is planar while K4 is not
(d) Neither K4 not Q3 is planar
Ans: (b)
Sol: (B)  Both are Planar graphs
Both graphs can be drawn on a plane without having any crossed edges.
Showing K₄ is Planar
Showing Q₃ is Planar

Q5: Which of the following statements is true for every planar graph on n vertices?  (2008)
(a) The graph is connected
(b) The graph is Eulerian
(c) The graph has a vertex-cover of size at most 3n/4
(d) The graph has an independent set of size at least n/3
Ans: (c)
Sol: Independent Set ≥ ⌈n/k⌉ where,
n is the number of vertices and k is the chromatic number
For any planar graph, k ≥ 3 and k ≤ 4, therefore, the Independent set is at least ⌈n/4⌉.
Hence (D) is false.
Now we know that size of Vertex Cover + Independent Set Number = n.
If Independent set number ≥ ⌈n/4⌉ then,
Vertex cover ≤ n − (n/4)
Vertex Cover ≤ 3n/4
Vertex Cover is at most 3n/4. So, (C) is the correct answer.

Q6: Let G be the non-planar graph with the minimum possible number of edges. Then G has  (2007)
(a) 9 edges and 5 vertices
(b) 9 edges and 6 vertices
(c) 10 edges and 5 vertices
(d) 10 edges and 6 vertices
Ans: (b)
Sol: Non planar graph with smallest number of edges is K3,3; it has 9 edges and 6 vertices
K5 is also non planar but it has 10 edges and 5 vertices.

Q7: Which one of the following graphs is NOT planar?  (2005)
(a) (b) (c) (d) Ans: (a)
Sol: We can form a planar graph for all except G1. Hence G1 is not planar graph.

Q8: Let G be a simple connected planar graph with 13 vertices and 19 edges. Then, the number of faces in the planar embedding of the graph is:  (2005)
(a) 6
(b) 8
(c) 9
(d) 13
Ans: (b)
Sol: f = e - n + 2 where f denotes number of faces E the number of edges n the number of vertices So f = 19 − 13 + 2 = 8 faces.