Let $n \ge 6$. Prove that it is not possible to partition the edges of $K_n$ into floor($\frac{n}{6}$) planar subgraphs.

Question

Any hints will be appreciated.

Here are some things I thought about:

• Since $K_n$ is a complete graph, it must be $(n - 1)$ regular
• The sum of the degree of all its vertices is $n(n - 1)$
• There are $n$ choose $2$ or $\frac{n(n-1)}{2}$ edges in $K_n$

I also thought maybe we can somehow use Kuratowski's Theorem. I just wonder how can I show that if we partitioned the graph into floor(n/6) subgraphs that at least one of its subgraphs must be an edge subdvision of K₅ or K_3,3, therefore, is nonplanar.

Or maybe if I could prove that at least one of the subgraphs with m vertices will have more than $(3m - 6)$ edges then that would work too. But I don't quite know how to start.

I also don't know if this question is related to the Ramsey' problem.