Generalizing Kuratowski's Theorem: Drawing Graphs on a Doughnut
By: Mihai Avram, Frank Lagoe, Theresa Kaufmann, Xin Li, and Cory Smith.
If you try to draw K_5 in the plane (or on a sphere) you will not be able to do it without crossing edges. Explain how on a doughnut K_5 and even K_6 can be drawn. Is K_7 possible? What about other surfaces such as a pretzel?
Introduction:
K_n graphs is an important concept in Graph Theory, but before we talk about K_n graphs we must elaborate on what a simple graph is. A simple graph is defined as a graph in which each edge connects a pair of distinct vertices and no two edges should connect the same pair of vertices. Each K_n group of graphs is a simple graph and is defined as a complete (each vertex is connected to all the other vertices) graph on n vertices. We can see some examples of K_n graphs below:
One question that once riddled Mathematicians for ages was whether K_5, K_6, and K_7 graphs are possible to draw on a plane, sphere, doughnut, or pretzel. In this report we use Euler’s Theorem stating that if a graph G is planar and connected, and if one chooses any plane representation, then (vertices of G) - (edges of G) + (faces of G) = 2, and Graph Theory and Kuratowski's Theorem to answer some of these questions.
Kuratowski's Theorem states that a finite graph is planar if and only if it does not subsume a subgraph which is a subdivision of K_5 or K_3,3.
An image of K_3,3 is shown below:
Theory:
Eulers formula can be used to derive a minimum value for the genus of a graph such that a complete graph can be embedded on a surface.
Another theorem derived from Euler’s formula states that “If a graph G has genus g, then G can be drawn without edge-crossing on every surface Sn for which ng, Therefore the value determined for previously is a minimum number that the graph of Kn can be embedded on.
Using the formula for lower bound of the genus we find that both K_5, and K_6 require a graph of at least S1. By our second derivative of Euler’s formula, any higher value graph will also allow for the embedding of K_5, and K_6. The pretzel surface is of form S2, therefore both K_5, and K_6 can be placed on to the pretzel surface, without any crossings. Illustrations are provided below:
Can a K_5 graph be planar in a Doughnut?
K_5 Graph:
K_5 in a plane: not possible to be planar → edges cross
K_5 in a doughnut: 3D object so the edges don’t cross. Theory section can also prove this.
Can a K_6 graph be planar in a Doughnut?
K_6 graph:
K_6 in a plane: Not possible to be planar because edges cross.
K_6 in a doughnut: 3D object so the edges don’t cross. Theory section can also prove this.
Can a K_5 graph be planar in a Pretzel?
Yes, this 3D model of a pretzel and the Theory section shows that it can be done.
Can a K_6 graph be planar in a Pretzel?
Yes, this 3D model of a pretzel and the Theory section shows that it can be done.
Are K_7 planar graphs possible to draw on a Pretzel or Doughnut?
For the complete graph of K_7 we find that the minimum Sn that it can be embedded on is S1, and so K_7 can occur on both the pretzel, and the doughnut. This is the highest order graph that may occur on on the doughnut however, this is the highest order complete graph that can be drawn on the donut. K_8 may be drawn on the pretzel, however K_9 requires a higher order surface.
References:
Rashid Bin Muhammad's Home Page. (n.d.). Rashid Bin Muhammad's Home Page. Retrieved April 27, 2014, from http://www.personal.kent.edu/~rmuhamma/GraphTheory/graphTheory.htm
Rosen, K. H. (2012). 10. Discrete Mathematics and its Applications (7th ed., ). Boston: WCB/McGraw-Hill.
