Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

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?)

If 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.

share|improve this answer
    
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 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 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 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.