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

2 Answers 2

5
  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
  • 0
    Yes, randomly. Usually, it's very easy to find graph, which is rather like $K_{3,3}$ or $K_5$. Then I try to find a path instead of lacking edges between some vertices.2012-12-06
3

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.

  • 0
    Now I understand.2012-12-13