###### Question 10623 – GATE 1987

June 2, 2024###### Question 17270 – NTA UGC NET JUNE 2023 Paper-1

June 2, 2024# Question 10586 – GATE 1989

Which of the following graphs is/are planner?

Correct Answer: A

Question 13 Explanation:

(i) G

→ Let us assume K

Let G be a connected planar graph with n vertices and m edges, and no triangles. Then m≤2n-4.

Where m=9, n=6

⇒ 9 ≤ 12 – 4

⇒ 9 ≤ 8, which is to be false, then K

(ii) G

(iii) Let us assume G

Where m=9, n=6

then 9 ≤ 12-4

9 ≤ 8 is False

So, G

Answer: Only G

_{1}is K_{33}which is planar graph with the minimum number of edges.→ Let us assume K

_{33}is a planar graph. Then it satisfy the useful corollary. As there is no triangle in K_{33}.Let G be a connected planar graph with n vertices and m edges, and no triangles. Then m≤2n-4.

Where m=9, n=6

⇒ 9 ≤ 12 – 4

⇒ 9 ≤ 8, which is to be false, then K

_{33}is non-planar graph.(ii) G

_{2}is a planar graph. Because it can be redrawn like as below.(iii) Let us assume G

_{3}be a planar graph then it also be satisfy useful corollary.Where m=9, n=6

then 9 ≤ 12-4

9 ≤ 8 is False

So, G

_{3}is non-planar graph.Answer: Only G

_{2}is planar graph.Theory Explanation is given below.

Subscribe

Login

0 Comments