1.3k views

Which one of the following graphs is NOT planar?

1. G1
2. G2
3. G3
4. G4
retagged | 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

You Number them first and then make planar(G1)

you can not make the planar graph

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

selected by
+1
I stuck with G4 but you explain really well

Thank you so much sir
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
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 &lt; = 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.

1
2