[Math] Planar and non-planar graphs, and Kuratowski’s Theorem

graph theoryplanar-graphs

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

Best Answer

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.

Related Solutions

[Math] Kuratowski’s theorem and non – planar graph

Affirmed.

I offer the following (hopefully constructive) criticisms:

You should recognise why this graph drawing is important, e.g. by writing:

"We can see that the original graph has a subgraph homeomorphic to $K_{3,3}$ by redrawing it as follows: [[blah blah blah]]. Therefore it's not planar by Kuratowski's Theorem."

There's (arguably) a better way to draw the second graph; see below:

Original graph

New graph drawing

These were drawn using TikZ. Here's the LaTeX code:

\begin{tikzpicture}
  \tikzstyle{vertex}=[circle,draw=black,fill=black!20,minimum size=18pt,inner sep=0pt]
  \draw (0,0) node (c){};

  \draw (c)++(0*360/4+135:3) node[vertex] (A){$A$};
  \draw (c)++(1*360/4+135:3) node[vertex] (C){$C$};
  \draw (c)++(2*360/4+135:3) node[vertex] (D){$D$};
  \draw (c)++(3*360/4+135:3) node[vertex] (B){$B$};

  \draw (c)++(0*360/4+135:1.5) node[vertex] (E){$E$};
  \draw (c)++(1*360/4+135:1.5) node[vertex] (G){$G$};
  \draw (c)++(2*360/4+135:1.5) node[vertex] (H){$H$};
  \draw (c)++(3*360/4+135:1.5) node[vertex] (F){$F$};

  \draw[ultra thick] (A) -- (B) -- (D) -- (C) -- (A);
  \draw[ultra thick] (A) -- (E) -- (H) -- (D);
  \draw[ultra thick] (B) -- (F) -- (G) -- (C);
  \draw[ultra thick] (E) -- (G);
  \draw (F) -- (H);
\end{tikzpicture}

and for the second drawing:

\begin{tikzpicture}
  \tikzstyle{vertex}=[circle,draw=black,fill=black!20,minimum size=18pt,inner sep=0pt]
  \draw (0,0) node (c){};

  \draw (c)++(0,3)++(2,0) node[vertex] (G){$G$};
  \draw (c)++(0,3) node[vertex] (A){$A$};
  \draw (c)++(0,3)++(-2,0) node[vertex] (D){$D$};

  \draw (c)++(-2,0) node[vertex] (E){$E$};
  \draw (c) node[vertex] (C){$C$};
  \draw (c)++(2,0) node[vertex] (B){$B$};

  \draw (c)++(-2,1.5) node[vertex] (H){$H$};
  \draw (c)++(2,1.5) node[vertex] (F){$F$};

  \draw[ultra thick] (A) -- (B) -- (D) -- (C) -- (A);
  \draw[ultra thick] (A) -- (E) -- (H) -- (D);
  \draw[ultra thick] (B) -- (F) -- (G) -- (C);
  \draw[ultra thick] (E) -- (G);
  \draw (F) -- (H);
\end{tikzpicture}

Graph Theory – Multipartite Graphs that are Not Planar

Note that the multipartite graph $K_{r_1,...,r_n}$ is not planar if $n\geq 5$, because it contains the multipartite graph $K_{1,1,1,1,1}$ as subgraph, and $K_{1,1,1,1,1}$ is nothing but the complete graph $K_5$.

On the other hand, the multipartite graph $K_{r_1,...,r_n}$ is not planar if there exists $i\neq j$ such that $r_1\geq 3$ and $r_j\geq 3$, because it contains the bipartite graph $K_{r_i,r_j}$ as subgraph, which also contains $K_{3,3}$ as the subgraph since $r_i,r_j\geq 3$.

Note also that the bipartite graph $K_{1,m}$ and $K_{2,n}$ are always planar. (Can you find planar drawings of them?)

Based on the above observation, we just need to examine each one of them to check whether they are planar or not.

Best Answer

Related Solutions

[Math] Kuratowski’s theorem and non – planar graph

Graph Theory – Multipartite Graphs that are Not Planar

Related Question