###### DSSSB TGT 2017

October 24, 2023###### GATE 2007

October 24, 2023# GATE 2007

Question 4 |

Let G be the non-planar graph with the minimum possible number of edges. Then G has

9 edges and 5 vertices | |

9 edges and 6 vertices | |

10 edges and 5 vertices | |

10 edges and 6 vertices |

Question 4 Explanation:

Using Euler’s formula we know that,

if n ≥ 3 then e ≤ 3n-6 (for planarity)

where n = no. of vertices

e = no. of edges

Now lets check the options.

A) e=9, n=5

9 ≤ 3(5) – 6

9 ≤ 15 – 6

9 ≤ 9

Yes, it is planar.

B) e=9, n=6

9 ≤ 3(6) – 6

9 ≤ 18 – 6

9 ≤ 12

Yes, it is planar.

iii) e=10, n=5

10 ≤ 3(5) – 6

10 ≤ 15 – 6

10 ≤ 9

No, it is not planar.

So, option C is non-planar graph.

iv) e=10, n=6

10 ≤ 3(6) – 6

10 ≤ 18 – 6

10 ≤ 12

Yes, it is planar.

if n ≥ 3 then e ≤ 3n-6 (for planarity)

where n = no. of vertices

e = no. of edges

Now lets check the options.

A) e=9, n=5

9 ≤ 3(5) – 6

9 ≤ 15 – 6

9 ≤ 9

Yes, it is planar.

B) e=9, n=6

9 ≤ 3(6) – 6

9 ≤ 18 – 6

9 ≤ 12

Yes, it is planar.

iii) e=10, n=5

10 ≤ 3(5) – 6

10 ≤ 15 – 6

10 ≤ 9

No, it is not planar.

So, option C is non-planar graph.

iv) e=10, n=6

10 ≤ 3(6) – 6

10 ≤ 18 – 6

10 ≤ 12

Yes, it is planar.

Correct Answer: C

Question 4 Explanation:

Using Euler’s formula we know that,

if n ≥ 3 then e ≤ 3n-6 (for planarity)

where n = no. of vertices

e = no. of edges

Now lets check the options.

A) e=9, n=5

9 ≤ 3(5) – 6

9 ≤ 15 – 6

9 ≤ 9

Yes, it is planar.

B) e=9, n=6

9 ≤ 3(6) – 6

9 ≤ 18 – 6

9 ≤ 12

Yes, it is planar.

iii) e=10, n=5

10 ≤ 3(5) – 6

10 ≤ 15 – 6

10 ≤ 9

No, it is not planar.

So, option C is non-planar graph.

iv) e=10, n=6

10 ≤ 3(6) – 6

10 ≤ 18 – 6

10 ≤ 12

Yes, it is planar.

if n ≥ 3 then e ≤ 3n-6 (for planarity)

where n = no. of vertices

e = no. of edges

Now lets check the options.

A) e=9, n=5

9 ≤ 3(5) – 6

9 ≤ 15 – 6

9 ≤ 9

Yes, it is planar.

B) e=9, n=6

9 ≤ 3(6) – 6

9 ≤ 18 – 6

9 ≤ 12

Yes, it is planar.

iii) e=10, n=5

10 ≤ 3(5) – 6

10 ≤ 15 – 6

10 ≤ 9

No, it is not planar.

So, option C is non-planar graph.

iv) e=10, n=6

10 ≤ 3(6) – 6

10 ≤ 18 – 6

10 ≤ 12

Yes, it is planar.

Subscribe

Login

0 Comments