I need to show this graph is not planar.
I've attempted to find a subgraph that is a subdivision of $K_5$ or $K_{3,3}$ but haven't been successful yet.
Prove this graph is not planar.
planar-graphs
Related Solutions
- Let's take bipartite graph $K_{3,3}$ with vertices $\{2,5,7\}$ in the first part and $\{1,3,6\}$ in the other and with edges: $(2,1); (2,3); (2,6); (5,1);(5,3);(5,6);(7,1);(7,3);(7,6)$. Next, in order to get $G_4$ graph we subdivide two edges: (5,3) and (7,1). It means that add new vertex on this edge. We add vertex 4 on the first edge and vertex 8 on the second. Now we don't have an $edge$ between vertices 5 and 3, but we have a $path$ between them. This is exactly what subdivision means. Then you can consider next two graphs in an analogous way.
Although the question has already been thoroughly answered, here is an unusual approach to checking if a graph is planar that I'm very fond of which works well here.
First, we notice that there's a cycle passing through all $12$ vertices:
(This method is only guaranteed to settle the question one way or the other if we find such a cycle, though for a cycle that passes through only most of the vertices it can still be very helpful.)
Now redraw the graph so that this cycle is arranged in a circle:
If there's a planar embedding of the graph, this circle has to appear in it somewhere, and so the only choices left to make for how to draw the graph are deciding, for each edge not in the cycle, whether it will be drawn as a chord inside the circle or outside the circle.
But the three highlighted edges all intersect each other. No matter which choices you make for them, either two of them will be on the inside (and intersect) or two of them will be on the outside (and intersect). So there is no planar embedding.
(In general, once the Hamiltonian cycle has been found - if it exists - deciding if the remaining edges can be drawn without crossing is straightforward. Begin with an arbitrary choice and then just make sure that if an edge is on the inside, all the edges it crosses are on the outside, and vice versa.)
Best Answer
Is this a subdivision of $K_{3,3}$?