edited by
7,721 views
31 votes
31 votes

Which of the following graphs is/are planar?

edited by

4 Answers

Best answer
36 votes
36 votes

$G_1$ is $K_{3,3}$ which is a non-planar graph with the minimum number of edges.

Proof: Let $K_{3,3}$ is a planar graph.
Therefore it must satisfy this useful corollary. As there is no triangle in  $K_{3,3}$.

  • Let $G$ be a connected planar simple graph with $n$ vertices and $m$ edges, and no triangles. Then $m \leq 2n - 4$

$m = 9, n = 6.$
$\implies 9 \leq12 - 4$
$\implies 9 \leq8,$ which is false. So our assumption that  $K_{3,3}$ is planar is false.

$G_2$ can be redrawn like this.

Therefore $G_2$ is a planar graph.

For $G_3$, we assume that it is a planar graph. Then it must satisfy the above corollary as it does not have a triangle.

$m = 9, n = 6.$
$\implies 9 \leq 12 - 4$

$\implies 9 \leq 8,$ which is false. So our assumption is wrong and $G_3$ is not a planar graph.

Note$: G_1$ and $G_3$ are isomorphic graphs. 

Ans: $G_2$ only.

edited by
13 votes
13 votes
graph G2 is planar because we can draw all its edges without crossing each other .
0 votes
0 votes

you can remember this points to solve this type of questions:

  1. Km,n is planar iff m<=2 or n<=2
  2. Q3 is planar as it has isomorphic structure G2 as shown in BEST answer below 
  3. G3 shown here is isomorphic with K 3,3 

Related questions

1 votes
1 votes
1 answer
1
makhdoom ghaya asked Nov 30, 2016
725 views
Consider the definition of macro $B,$ nested within the definition of a macro $A.$ Can a call to macro $B$ also appear within macro $A?$ If not, why not? If yes, explain ...