5
$\begingroup$

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

$\endgroup$

2 Answers 2

Reset to default
5
$\begingroup$
  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
$\endgroup$
9
  • $\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, 2012 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, 2012 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, 2012 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, 2012 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, 2012 at 21:27
3
$\begingroup$

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.

$\endgroup$
3
  • $\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, 2012 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, 2012 at 22:28
  • $\begingroup$ Now I understand. $\endgroup$
    – Dream Box
    Dec 13, 2012 at 15:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .