The Gateway to Computer Science Excellence
+4 votes
800 views

Two graphs A and B are shown below: Which one of the following statements is true?

  1. Both A and B are planar
  2. Neither A nor B is planar
  3. A is planar and B is not
  4. B is planar and A is not
in Graph Theory by Veteran (105k points)
recategorized by | 800 views
0
Ma'am you missed out the Graphs

2 Answers

+3 votes
Best answer

Planar Graph:-A graph G is planar if it can be drawn in the plane in such a way that no two edges meet each other except at a vertex to which they are incident.

Here Both S1 and S2 are Planar graph .Here no edges cross each other.

 

 

Hence,Option(A)Both A and B Planar.

by Boss (41k points)
selected by
0 votes

Constructing planar version of given graph is quite time consuming. We can solve such questions quickly using the relation :

If E is the number of edges and V is the number of vertices, and  E<= 3(V-2),  graph is  planar, otherwise it is Not Planar.

  1. A) V=4; E=6; 3*(V-2)=3(4-2)=6=E  //Planar
  2. B) V=8; E=12 3*(V-2)=3(8-2)=18               E=12<18   //Planar

answer : Both A and B are planar

by Boss (32.5k points)
0
But this solution is not applicable on Peterson graph which is not planar
0
Thanks
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,645 questions
56,609 answers
195,893 comments
102,319 users