graph theoryplanar-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.
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
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.