The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+9 votes
1.3k views

Which one of the following graphs is NOT planar?

  1. G1
  2. G2
  3. G3
  4. G4
asked in Graph Theory by Boss (18.3k points)
retagged by | 1.3k views
0

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

??

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

@Pranav Madhani 

You Number them first and then make planar(G1)

you can not make the planar graph

2 Answers

+9 votes
Best answer

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

answered by Boss (40.7k points)
selected by
+1
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
answered by Boss (14.4k points)
0
yes G1 is non planar
+1

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)

0
If a graph is connected and does not have any cycle or say triangle then just try to use formula   e < = 2n-4 .........
0
@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.
+1
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.
0

It is necessary condition to be planar not sufficient.

 

Answer:

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

44,147 questions
49,639 answers
163,292 comments
65,807 users