A graph $G$ is planar if and only if every subdivision of $G$ is planar.

A graph $G$ is planar if and only if it contains no subdivision of $K_{3,3}$ or $K_5$.

A subdivision of an edge $e$ in $G$ is a substitution of a path for $e$. We say that a graph $H$ is a subdivision of $G$ if $H$ can be obtained from $G$ by a finite sequence of subdivisions.

Using Kuratowski's Theorem, I need to show that the graphs below are non planar

enter image description here

I know how the $K_{3,3}$ and $K_5$ look like but the subdivision part lost me. I'd appreciate as much help as possible. Thank you

  1. 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. enter image description here
  • $\begingroup$ I don't understand what you did right there, I mean, you explain how to subdivide a graph but what about the $G_4$ graph? There's no edge between 5 and 3.. $\endgroup$ – Dream Box Dec 6 '12 at 20:34
  • $\begingroup$ @Dream Box:Yes, there isn't. But when we subdivide this edge, we get as a result two edges(in this case instead (5,3) we have (5,4) and (4,3) after subdivision of (5,3)). After subdivision there vanishes the edge we subdivide, and two new edges appear. Now it's clear? $\endgroup$ – unknown Dec 6 '12 at 20:57
  • $\begingroup$ I get the subdivision, from one edge,you make two by adding a vertex. But then using the theorem, how do I show that the graph is not planar? $\endgroup$ – Dream Box Dec 6 '12 at 21:14
  • $\begingroup$ It is know that $K_{3,3}$ and $K_5$ graps are non-planar. Kuratowski's Theorem: A finite graph is planar if and only if it does not contain a subgraph that is a subdivision of $K_5$ or $K_{3,3}$. In the answer above I show, that we can make some subdivisions in $K_{3,3}$ and get a graph which is a subgraph of $G_4$ $\endgroup$ – unknown Dec 6 '12 at 21:25
  • $\begingroup$ I knew that about those graphs. Oh so the last thing, is a subdivision? So $G_4$ is non planar cause it has a ^ region, the 6,center,4 one. Or am I wrong? $\endgroup$ – Dream Box Dec 6 '12 at 21:27

Note that no subdivision is needed for $G_5$. There is a way to choose three vertices $a,b,c$ from $1,2,3,4$, and three vertices $x,y,z$ from $5,6,7,8,9$, in such a way that each of the vertices $a,b,c$ is adjacent to each of the vertices $x,y,z$. That's a $K_{3,3}$, and you're done.

$G_6$ doesn't need any subdivisions, either. In fact, there's a way to see it as a $K_{3,4}$ with some extra edges.

  • $\begingroup$ So you mean if I choose for example, 4,2,1 and 5,7,8 ,the graph is a $K_3_,3$? That is what it appears to me. At $G_6$ what edges are missing? I don't seem to find them $\endgroup$ – Dream Box Dec 12 '12 at 13:23
  • $\begingroup$ Yes, each of 4, 2, 1 is adjacent to each of 5, 7, 8 so the subgraph induced by those vertices is a $K_{3,3}$. I don't understand your question about $G_6$ --- I didn't say any edges were missing, I said it contains a $K_{3,4}$. $\endgroup$ – Gerry Myerson Dec 12 '12 at 22:28
  • $\begingroup$ Now I understand. $\endgroup$ – Dream Box Dec 13 '12 at 15:24

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.