GATE CSE 2005 | Question: 47

Question

Which one of the following graphs is NOT planar?

 

• A. G1
• B. G2
• C. G3
• D. G4

Comments

A finite graph is planar if and only if it does not contain a subgraph that is a subdivision of the complete graph K5 or the complete bipartite graph K3,3 (utility graph). Source

G1 is exactly K3,3 but drawn in a different way. See this

---

here we can easily tell g1 is not planar because in g1 one edge is going through two non edges that means it is a cross edge so it is non planar

---

G1 is not planar

Answer 1

​

We can form a planar graph for all except G1. Hence G1 is not planar graph. 

Comments

I stuck with G4 but you explain really well

Thank you so much sir

Answer 2

I was in a confusion between G1 and G4 but by wisely editing the edges i can form a planar graph for G4 but am unsucessful to make G1 a planar graph so G1 is non planar

Comments

these corollary are used only to check if a graph is no-planar or not. That means if some graph satisfies these dosnt means it is planar but it dissatisfies guarantees that it is non planar.

---

It is necessary condition to be planar not sufficient.

 

---

Here e<=2n-4 condition for graph containing no triangle(bi-partite) can be used for checking non-planar. But doesn't always work, can only be used in contrapositive sense.

(Simple & Planar & No Triangle → e<=2n-4) (→ is implication)

e=9 and n=6,

e<=2n-4

9<=2*6-4

9<=8 is false, So LHS should also be false.

We know Graph is simple and contains No triangle, then planar condition has to be false , making G1 non-planar.