The Gateway to Computer Science Excellence
+11 votes

Which one of the following graphs is NOT planar?


  1. G1
  2. G2
  3. G3
  4. G4
in Graph Theory by Boss (17.5k points)
edited by | 1.8k views

why is g1 not planar? We can create planar structure of G1 also


No, check again.Edges in your graph different from given graph.
not isomorphic to original graph.
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
his graph contain triangle but original doesnt.

@Pranav Madhani 

You Number them first and then make planar(G1)

you can not make the planar graph


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

2 Answers

+14 votes
Best answer

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

by Boss (41.2k points)
selected by
I stuck with G4 but you explain really well

Thank you so much sir
+4 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
by Boss (14.4k points)
yes G1 is non planar

if G1 is non-planar, then it shouldn't satisfy 3v-e>=6 this inequality right ?
but it does
3*6-9>=6 --> 9>=6 (Satisfied)

If a graph is connected and does not have any cycle or say triangle then just try to use formula   e < = 2n-4 .........
@eyeamgj  i dont think e<=2n-4 will work because it is for bipartite graphs only ..and complete graphs will have cycles in it still follow e<3n-6.
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.



Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,321 answers
105,155 users