UGC NET CSE | June 2012 | Part 3 | Question: 72

Question

$G_1$ and $G_2$ are two graphs as shown:

• A. Both $G_1$ and $G_2$ are planar graphs
• B. Both $G_1$ and $G_2$ are not planar graphs
• C. $G_1$ is planar and $G_2$ is not planar
• D. $G_1$ is not planar and $G_2$ is planar

Answer 1

Planar Graph :- A planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other.

Here only G₂ is planar graph.

Hence,Option(D)G₁ is not planar and G₂ is planar.

Answer 2

The option will be (D). Both G1 is not Plannar but is plannar graph. In Plannar graphs, no two of its edges intersect.

Comments

why G₂ is not planar ?

---

Thanks for correcting me. G1 is not plannar but G2 is Plannar. So the answer will be option (D).

Answer 3

No: of vertices in G2= 6

No:of edges in G2=12

By the corollary of Euler's formula, the following inequality must hold to say that G2 is planar.

e less than or equal to 3n-6

12 less than or equal to 3*6-6=12

12=12 ☑️

Therefore, G2 is planar.

Comments

but graph 1iz also satisfying  the same formula

9<= (18-6)

then how ??? plz elaborate  liitle

---

In G1 we will apply e<=2*v-4  bcz NO CIRCUIT OF LENGTH IS 3 SO

E=9 FOR G1

9<=2*6-4

9<=8 WHICH IS NOT SATISFY  therefore G1 is NON-Planar 

*** BY the Brute force approach u can see that BF & CD WILL INTERSECT SO AGAIN G1 WILL BE NON PLANAR 

BUT in Graph G2 there is a circuit of length 3 so e<=3*v-6 which will applicable most of the time 

12<=12 

---

Kindly discard the above explanation by me..

Here u hav an easy way to check whether a graph is planar or not...

Any planar graph is 4- colorable.

i.e., color every non-adjacent vertex with same colors.. if u could color every vertex with a min of 4 colors, then it would be planar.. 👍

---

Both the conditions mentioned above are necessary but not sufficient.. they can be used only to prove a graph is not planar.. they cannot be used to confirm a graph is planar..😔