recategorized by
2,197 views
5 votes
5 votes

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
recategorized by

2 Answers

Best answer
3 votes
3 votes

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
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

Answer:

Related questions

4 votes
4 votes
3 answers
1
go_editor asked Jul 8, 2016
4,161 views
$G_1$ and $G_2$ are two graphs as shown:Both $G_1$ and $G_2$ are planar graphsBoth $G_1$ and $G_2$ are not planar graphs$G_1$ is planar and $G_2$ is not planar$G_1$ is no...
26 votes
26 votes
3 answers
2
gatecse asked Aug 5, 2014
9,967 views
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...
1 votes
1 votes
1 answer
4
go_editor asked Jul 13, 2016
2,958 views
A* algorithm is guaranteed to find an optimal solution ifh’ is always 0g is always 1h’ never overestimates hh’ never underestimates h