Multipartite graphs which are not planar

Question

Please take a look at these definitions:

A multipartite graph is a graph of the form $K_{r_1,\ldots, r_n}$ where $n > 1$, $r_1, \ldots, r_n\ge 1$, such that

• The set of nodes of the graph is the disjoint union of n sets: $V = V_1 \cup\cdots\cup V_n$, and $|V_i|=r_i$ for all $1\le i\le n$.

• The set of nodes of the graph is the set of all possible connections between nodes in that do no belong to the same set $S_i$. Formally:

  $$E= \{(x,y)\mid x \in S_i, y \in S_j, i \ne j\}$$

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$.

I need to determine all multipartite graphs that are not planar.

Answer 1

Here's a hint: if $n \geq 5$, it's clear that $G = K_{r_1, \ldots, r_n}$ contains a $K_5$. Moreover, if at least two of the $r_i$s are at least 3, then $G$ clearly contains a $K_{3, 3}$. That leaves fairly few cases left to check. You might start on them by deciding whether $K_{2, 2, 2}$ is planar.

Answer 2

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.