17 votes 17 votes K4 and Q3 are graphs with the following structures. Which one of the following statements is TRUE in relation to these graphs? K4 is a planar while Q3 is not Both K4 and Q3 are planar Q3 is planar while K4 is not Neither K4 nor Q3 is planar Graph Theory gatecse-2011 graph-theory graph-planarity normal + – go_editor asked Sep 29, 2014 edited May 10, 2019 by Lakshman Bhaiya go_editor 6.9k views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply Nisha Bharti commented Jan 12, 2023 reply Follow Share 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 0 votes 0 votes abir_banerjee commented Sep 6, 2023 reply Follow Share @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 . 3 votes 3 votes Please log in or register to add a comment.
Best answer 29 votes 29 votes (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}$ Manu Thakur answered Nov 19, 2014 edited May 10, 2019 by Lakshman Bhaiya Manu Thakur comment Share Follow See all 3 Comments See all 3 3 Comments reply Kishan K. Verma commented Dec 28, 2017 reply Follow Share Please explain how Q3 can be drawn without crossing edges. @Manu Thakur 0 votes 0 votes Manu Thakur commented Dec 28, 2017 reply Follow Share kishan, now check. 0 votes 0 votes Kishan K. Verma commented Dec 29, 2017 reply Follow Share Thanks. Got it. 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes K4 and Q3 are graphs with the following structures . akshay_123 answered Sep 3, 2023 akshay_123 comment Share Follow See all 0 reply Please log in or register to add a comment.