So. First we have to figure out what "thickness" means. The book defines thickness of a simple graph G as the smallest number of planar subgraphs of G that have G as their union. This means that if a graph is planar, its thickness is one. However if a graph is not planar, then we have to figure out how many different graphs we have to divide it into in order to make each individual subgraph to be planar.

Since we know that K_(3,3) is not planar, it cannot have a thickness of one.

We then need to divide the K_(3,3) into two different subgraphs that are planar. Try splitting it up into one graph as two outer of one side, linked to all of the points on the other side; and then the second graph as the middle point of the incomplete side, with the three points on the other side. Then show that both of these subgraphs are planar.

Alumni Liaison

Questions/answers with a recent ECE grad

Ryne Rayburn