Planar Graph Applet I

Exploring planarity of complete graphs and complete bipartite graphs

The following graphs are either complete graphs or complete bipartite graphs. For each graph, identify it as K_n or K_n,m, and determine if it is planar or not by dragging the nodes until the edges of the graph do not cross, if possible. Warning: If you do not manage to arrange the edges so that they do not cross, you have not proven that the graph is non-planar. In this case, your answer is simply an informed conjecture.

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.

Copyright 2005 by Douglas E. Ensley. See http://www.ship.edu/~deensl/DiscreteMath/ for more Flash applets for Discrete Mathematics. Please direct questions and comments to deensl@ship.edu.