Exercises on Planarity

The following graphs are either complete graphs or complete bipartite graphs. For each graph, identify it as Knor Kn,m, and determine if it is planar or not.

Discussion Problems

  1. Make a conjecture about which complete graphs are planar and which are non-planar.
  2. Make a conjecture about which complete bipartite graphs are planar and which are non-planar.