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?
$\begingroup$
$\endgroup$
2
-
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éophileMay 15, 2015 at 13:21
-
$\begingroup$ Combined with Euler's formula, I know the number of faces must always be the same, regardless of layout? $\endgroup$– MarkMay 15, 2015 at 13:23
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
5
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:
answered May 15, 2015 at 13:23
-
$\begingroup$ How would I label vertices in such a way to satisfy this? $\endgroup$– MarkMay 15, 2015 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$ May 15, 2015 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$ May 15, 2015 at 14:25
-
$\begingroup$ The smoothing of your graph contains $K_{3,3}$. So your graph is not planar. $\endgroup$ May 15, 2015 at 15:51
-
$\begingroup$ @PerryElliott-Iverson Yes, I figured that out after filling with drawings 3-4 sheets of paper :) $\endgroup$ May 15, 2015 at 15:56
$\begingroup$
$\endgroup$
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.
