Multipartite graphs which are not planar

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.

-

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.

-
Why $K_2,_2,_2$ ? Could you give me more details? – Dream Box Dec 12 '12 at 13:18
I suppose that I should have said $K_{2,2,1}$. As Paul noted in his answer, $K_{1,m}$ and $K_{2,m}$ are always planar, so tripartite graphs are the next case to consider. – Andrew Uzzell Dec 12 '12 at 14:59
Well didn't he say that if r is >= 3 that means it's not planar? tripartite graphs would make r be 3 right? So that makes them non planar. – Dream Box Dec 12 '12 at 19:30
Tripartite means having three parts (i.e., if $G = K_{r_1, \ldots, r_n}$, then $n = 3$), just as bipartite means having two parts (i.e., $n = 2$). – Andrew Uzzell Dec 12 '12 at 20:48
Is this a tripartite? gyazo.com/b57fe180a623d0bb8513a85be716e7c9 So what other graphs do I need to decide if they are planar? If that is tripartite, that means it's not planar. I drew $K_2_,2_,2$ just like the tripartite in the picture tho added another vertex on the same line as vertex 3. Am I not getting something here? – Dream Box Dec 13 '12 at 19:08

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.

-
Well aren't they planar since the edges do not intersect? $K_1,_m$ and $K_2,_m$ that is. So what you're saying is that the multipartite graphs are planar only for r=1 and r=2? – Dream Box Dec 12 '12 at 13:17

The only cases for the multipartite graph $K_{r_1,\ldots, r_n}$ to be planar are as follows:

case 1: $n=2$, $r_1\leq2$,

case 2: $n=3$, $r_1\geq3,r_2=r_3=1$ or $r_1,r_2,r_3\leq2$,

case 3: $n=4$, $r_1=1$ or $2,r_2=r_3=r_4=1$.

`

-