search
Log In
4 votes
966 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
recategorized by
966 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.


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

0
But this solution is not applicable on Peterson graph which is not planar
0
Thanks
Answer:

Related questions

3 votes
3 answers
1
1.5k views
G1 and G2 are two graphs as shown: Both G1 and G2 are planar graphs Both G1 and G2 are not planar graphs G1 is planar and G2 is not planar G1 is not planar and G2 is planar
asked Jul 8, 2016 in Graph Theory jothee 1.5k views
0 votes
0 answers
2
607 views
Are the following topics necessary/ apt to study for gate.(Bold items are explicitly mentioned in gate syllabus document) Connectivity Matching Coloring Cuts Covering Independent Sets Planar Graphs Isomorphism Walks, Trails, Paths, Cycles and Circuits in Graph Graph measurements: length ... all of these is taking a lot of time. Can anyone please recommend a reliable and simple resource to go with.
asked Dec 29, 2018 in Graph Theory Krishna Sai Vootla 607 views
1 vote
0 answers
3
164 views
In a connected 3 regular graph, every planar region is bounded by exactly 5 edges, then count no of edges?
asked Dec 21, 2018 in Graph Theory Shamim Ahmed 164 views
0 votes
1 answer
4
508 views
Let G be a simple connected planar graph with 14 vertices and 20 edges. Number of closed regions in planar embedding of the graph is ?
asked Dec 2, 2018 in Graph Theory Na462 508 views
...