GATE CSE 2011 | Question: 17

Question

K4 and Q3 are graphs with the following structures.

Which one of the following statements is TRUE in relation to these graphs?

• A. K4 is a planar while Q3 is not
• B. Both K4 and Q3 are planar
• C. Q3 is planar while K4 is not
• D. Neither K4 nor Q3 is planar

Comments

For planarity check we can use the property m<=2n-4 then why the result of K4 is 6<=4 means it is not planar

---

@Nisha Bharti we use e <= 2v – 4 only when we have connected planar graph with v>=3 and there is no cycle in form of triangle in the graph although the graph can be cyclic . 

In , general , for any connected planar graph with v>=3 , we can say that :- 

e <= 3v-6 .

where e is the number of edges and v is the number of vertices .  

Answer 1

(B)  Both are Planar graphs
Both graphs can be drawn on a plane without having any crossed edges.

$\text{Showing $K_{4}$ is Planar}$

                

$\text{Showing $Q_{3}$ is Planar}$

                            

Comments

Please explain how Q3 can be drawn without crossing edges. @Manu Thakur

---

kishan, now check.

---

Thanks. Got it.

Answer 2

K4 and Q3 are graphs with the following structures

.