A characterisation of planar complete $k$-partite graphs

Question

The complete $k$-partite graph $K_{n_1,n_2,\dots,n_k}$ has vertex set $V=V_1\dot\cup V_2\dot\cup\dots\dot\cup V_k$, where $V_1,\dots,V_k$ are disjoint sets with $|V_i|=n_i$, and each vertex $v\in V_i$ is connected to all vertices of $V\setminus V_i,i=1,2,\dots,k$. Describe all $k$-tuples $(n_1,n_2,\dots,n_k)$ of natural numbers, $k=1,2,\dots$, such that $K_{n_1,n_2,\dots,n_k}$ is a planar graph.

Answer 1

All planar $k$-partite graphs must have $k<5$; if $k\ge5$ the graph will contain the non-planar $K_{1,1,1,1,1}\simeq K_5$.

Now suppose $k=4$. The partition orders in a planar 4-partite graph must all be less than 3; $K_{3,1,1,1}$ is non-planar by virtue of having $K_{3,3}$ as a subgraph and all 4-partite graphs with one partition of order at least 3 will have $K_{3,1,1,1}$ as a subgraph. Therefore the partition orders can only be one or two, but $K_{2,2,1,1}$ is already non-planar by containing $K_{3,3}$ as a subgraph. Thus the only planar 4-partite graphs are $K_{2,1,1,1}\simeq K_5-e$ and $K_{1,1,1,1}\simeq K_4$.

Moving on to tripartite graphs, $K_{n,1,1}$ is planar for all natural $n$, but $K_{3,2,1}$ is non-planar because it is $K_{3,3}+e$. Therefore the only planar tripartite graph with exactly one partition of order one is $K_{2,2,1}$. If all the partitions have at least two vertices, only $K_{2,2,2}$ is planar (it is the octahedral graph); $K_{3,2,2}$ is non-planar by containing $K_{3,3}$ as a subgraph.

Bipartite graphs $K_{m,n}$ are very easy to characterise: they are non-planar iff $m,n\ge3$. Finally, for just one partition we simply have planar, empty graphs.

In summary, the $k$-tuples associated with planar $k$-partite graphs are (where $n$ is a natural number):

• $k=4$: $(2,1,1,1),(1,1,1,1)$
• $k=3$: $(n,1,1),(2,2,2),(2,2,1)$
• $k=2$: $(n,2),(n,1)$
• $k=1$: $(n)$