Showing planarity of graphs

Question

I am trying to show $G_3$ is planar. I have constructed $G'_3$ as shown. Is it correct to say that by the Jordan curve theorem, $G_3$ cannot be planar, as any drawing will cause edges to overlap. Therefore it is non-planar?

Answer 1

You have the Kuratowski theorem which says the following.

A finite graph is planar if and only if it does not contain a sub-graph that is a subdivision of $K_5$ (the complete graph on five vertices) or $K_{3,3}$ (the complete bipartite graph on six vertices, three of which connect to each of the other three, also known as the utility graph).

Just figure out if your graph matches or not the conditions of this theorem. That would be more rigorous than making drawings.

OK, here is the initial drawing of your graph.

Now, if you draw it in the way shown below, it's still the same graph, but it's obvious now that after its smoothing (which removes vertex G), the graph will contain $K_{3,3}$. So the given graph is not a planar graph.

See also:

Planar graph
Homeomorphism, subdivision, smoothing

Answer 2

The graph $G_3$ is nonplanar. It contains as a graph minor $K_{3,3}$. To see this, see my picture:

The first arrow is a rearrangement of the vertices of $G_3$. The second arrow is the desired deletion and contraction to obtain the minor $G_3^{\prime}\approx K_{3,3}$. Hence $G_3$ is not planar by Kuratowski's Theorem.