Complete bipartite graphs

Task number: 4246

Show that the graph \( K_{m, n} \) is planar if and only if \( \min \{m, n \} \le 2 \).

  • Solution

    If \( \min \{m, n \} \ge 3 \), then the graph contains \( K_{3{,}3} \) as a subgraph and is not planar according to the Kuratowski’s theorem.

    The graph \( K_{2, n} \) can be drawn in a planar way, see the picture. Graphs \( K_{1, n} \) and \( K_{0, n} \) are its subgraphs, so they are also planar.

    complete bipartite
Difficulty level: Easy task (using definitions and simple reasoning)
Proving or derivation task
Cs translation
Send comment on task by email