15 votes 15 votes Which one of the following graphs is NOT planar? G1 G2 G3 G4 Graph Theory gatecse-2005 graph-theory graph-planarity normal + – gatecse asked Sep 21, 2014 • edited May 16, 2019 by Pooja Khatri gatecse 8.3k views answer comment Share Follow See all 7 Comments See all 7 7 Comments reply Pranav Madhani commented Dec 7, 2017 reply Follow Share why is g1 not planar? We can create planar structure of G1 also ?? 0 votes 0 votes LeenSharma commented Dec 7, 2017 reply Follow Share No, check again.Edges in your graph different from given graph. 1 votes 1 votes Rupendra Choudhary commented Dec 22, 2017 reply Follow Share not isomorphic to original graph. 0 votes 0 votes joshi_nitish commented Dec 22, 2017 reply Follow Share in your graph two vertices are having degree 4 and two vertices are having degree 2 but in actual G1 all vertices are having degree=3 0 votes 0 votes Anu007 commented Dec 22, 2017 reply Follow Share his graph contain triangle but original doesnt. 0 votes 0 votes Lakshman Bhaiya commented Jan 29, 2018 reply Follow Share @Pranav Madhani You Number them first and then make planar(G1) you can not make the planar graph 0 votes 0 votes rawan commented Jan 10, 2019 reply Follow Share 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 1 votes 1 votes Please log in or register to add a comment.
Best answer 18 votes 18 votes We can form a planar graph for all except G1. Hence G1 is not planar graph. LeenSharma answered Dec 2, 2015 • edited Aug 1, 2021 by S k Rawani LeenSharma comment Share Follow See all 2 Comments See all 2 2 Comments reply Lakshman Bhaiya commented Jan 29, 2018 reply Follow Share I stuck with G4 but you explain really well Thank you so much sir 1 votes 1 votes Hira Thakur commented Oct 11, 2023 reply Follow Share there is any other method exists for checking the planner graph?? 0 votes 0 votes Please log in or register to add a comment.
5 votes 5 votes 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 Bhagirathi answered Sep 21, 2014 Bhagirathi comment Share Follow See all 7 Comments See all 7 7 Comments reply Show 4 previous comments raviyogi commented Nov 3, 2017 reply Follow Share 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. 1 votes 1 votes Prince Singh 1 commented Oct 25, 2018 reply Follow Share It is necessary condition to be planar not sufficient. 0 votes 0 votes Arpit Patel commented Jan 11, 2022 reply Follow Share 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. 0 votes 0 votes Please log in or register to add a comment.