2
$\begingroup$

Please take a look at these definitions:

A multipartite graph is a graph of the form $K_{r_1,\ldots, r_n}$ where $n > 1$, $r_1, \ldots, r_n\ge 1$, such that

  • The set of nodes of the graph is the disjoint union of n sets: $V = V_1 \cup\cdots\cup V_n$, and $|V_i|=r_i$ for all $1\le i\le n$.

  • The set of nodes of the graph is the set of all possible connections between nodes in that do no belong to the same set $S_i$. Formally:

    $$E= \{(x,y)\mid x \in S_i, y \in S_j, i \ne j\}$$

A graph $G$ is planar if and only if every subdivision of $G$ is planar. A graph $G$ is planar if and only if it contains no subdivision of $K_{3,3}$ or $K_5$.

I need to determine all multipartite graphs that are not planar.

3 Answers 3

1

The only cases for the multipartite graph $K_{r_1,\ldots, r_n}$ to be planar are as follows:

case 1: $n=2$, $r_1\leq2$,

case 2: $n=3$, $r_1\geq3,r_2=r_3=1$ or $r_1,r_2,r_3\leq2$,

case 3: $n=4$, $r_1=1$ or $2,r_2=r_3=r_4=1$.

`

3

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.

  • 0
    Well aren't they planar since the edges do not intersect? $K_1,_m$ and $K_2,_m$ that is. So what you're saying is that the multipartite graphs are planar only for r=1 and r=2?2012-12-12
2

Here's a hint: if $n \geq 5$, it's clear that $G = K_{r_1, \ldots, r_n}$ contains a $K_5$. Moreover, if at least two of the $r_i$s are at least 3, then $G$ clearly contains a $K_{3, 3}$. That leaves fairly few cases left to check. You might start on them by deciding whether $K_{2, 2, 2}$ is planar.

  • 0
    Why $K_2,_2,_2$ ? Could you give me more details?2012-12-12
  • 0
    I suppose that I should have said $K_{2,2,1}$. As Paul noted in his answer, $K_{1,m}$ and $K_{2,m}$ are always planar, so tripartite graphs are the next case to consider.2012-12-12
  • 0
    Well didn't he say that if r is >= 3 that means it's not planar? tripartite graphs would make r be 3 right? So that makes them non planar.2012-12-12
  • 0
    *Tripartite* means having three parts (i.e., if $G = K_{r_1, \ldots, r_n}$, then $n = 3$), just as *bipartite* means having two parts (i.e., $n = 2$).2012-12-12
  • 0
    Is this a tripartite? http://gyazo.com/b57fe180a623d0bb8513a85be716e7c9 So what other graphs do I need to decide if they are planar? If that is tripartite, that means it's not planar. I drew $K_2_,2_,2$ just like the tripartite in the picture tho added another vertex on the same line as vertex 3. Am I not getting something here?2012-12-13
  • 0
    Yes, that graph is tripartite. In order to determine whether that graph is planar, you should check whether it satisfies the definition above. Namely, if it's non-planar, you should show that it contains a subdivision of either $K_5$ or $K_{3,3}$, and if it's planar, you should show that it does not.2012-12-13
  • 0
    After checking the tripartite, what comes next?2012-12-13