5
$\begingroup$

enter image description here

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?

$\endgroup$
  • 4
    $\begingroup$ It is not enough, because how do you know there wasn't a better choice of position for the vertices and edges so far in $G_3'$? $\endgroup$ – Théophile May 15 '15 at 13:21
  • $\begingroup$ Combined with Euler's formula, I know the number of faces must always be the same, regardless of layout? $\endgroup$ – Mark May 15 '15 at 13:23
9
$\begingroup$

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.

drawing 1

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.

drawing 2

See also:

Planar graph
Homeomorphism, subdivision, smoothing

$\endgroup$
  • $\begingroup$ How would I label vertices in such a way to satisfy this? $\endgroup$ – Mark May 15 '15 at 13:24
  • $\begingroup$ @user43290 Just play a bit with it, see if it contains a sub-division of $K_5$ or $K_{3,3}$. Try also to do some smoothing on your graph e.g. that vertex at 3 o'clock (that has a degree of 2) can be removed by smoothing. $\endgroup$ – peter.petrov May 15 '15 at 13:33
  • $\begingroup$ @peter.petrov It's not planar. Delete the rightmost two edges in the drawing in the OP that are crossing one another to get a $K_{3,3}$ subdivision. $\endgroup$ – Perry Elliott-Iverson May 15 '15 at 14:25
  • $\begingroup$ The smoothing of your graph contains $K_{3,3}$. So your graph is not planar. $\endgroup$ – peter.petrov May 15 '15 at 15:51
  • $\begingroup$ @PerryElliott-Iverson Yes, I figured that out after filling with drawings 3-4 sheets of paper :) $\endgroup$ – peter.petrov May 15 '15 at 15:56
5
$\begingroup$

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.