# Planar complete tripartite graphs

For which values of $r$, $s$, and $t$ is the complete tripartite graph $K_{r,s,t}$ planar?

Obviously I want to look for either a $K_5$ or a $K_{3,3}$ in order to show that a specific graph is non-planar. If a graph doesn't have either of these than it is planar. However, I'm unsure how to approach this in the general case without drawing out every possible tripartite graph until I find some non-planar ones.

-

Without loss of generality assume $r\ge s\ge t$.

If $r\ge 3$, and $s+t\ge 3$ then the graph is not planar (why?)

In the cases $r\le 2$ or $s+t\le 2$, you should be able to find a strategy to draw the graph in a plane.

-
Because in the case of $r\geq 3$ and $s+t \geq 3$ there exists a $K_{3,3}$. We need not be concerned with a $K_5$ because by the definition of $n$-partedness a $K_5$ shouldn't exist, correct? – audiFanatic Apr 6 '14 at 21:40
Let me rephrase that last part. We need not concern ourselves with a $K_5$ because a $K_5$ cannot exist in an $n$-partite graph for $n\leq 4$ by definition. It can exist in a 5-partite graph or above. – audiFanatic Apr 6 '14 at 22:15
@audiFanatic: A 3-partite graph cannot contain $K_5$ as a subgraph, but a priori there isn't anything that prevents it from having it as a minor. And indeed it is easy to see that $K_{n,n}$ always has a $K_n$ minor. Instead of trying to argue that the $r\le 2$ or $s+t\le 2$ graphs can have no forbidden minors, it's much easier simply to describe how to draw them. – Henning Makholm Apr 6 '14 at 22:31

As noted in Henning Makholm answer, we have the following cases:

a) $r \geq 3$, $s+t \leq 2$

b)$r \leq 2$, $s+t \leq 4$.

In both the cases you can show that the graph is planar.

-