But if K3,3 were planar, it would have a natural orientation inherited from the plane, hence could not be filled with a nonorientable surface. (If K_3,3 were imbedded in the plane, the path around the Moebius strip would now appear to follow a patchwork of orientable areas, and so would not reverse orientation.) Therefore K_3,3 is nonplanar.

I think this is interesting, because the other two dimensional embedding mentioned (in a torus) can't be used so directly to prove K_3,3 is nonplanar, because the torus is orientable. Perhaps other topological properties of the torus could be used instead, but none is as obviously incompatible with a plane embedding as nonorientability.

The same trick works for K_5 as well: Taking the vertices 4 at a time you can see trapezoidal strips that you can think of as segments of a Moebius strip. Follow each strip to the edge and imagine that the paper folds under and conects to the next trapezoid. After going around 5 times, you have of course a Moebius strip because you've made an odd number of folds. To draw this graph on a Moebius strip, place 5 equally spaced points along its edge and connect them across the strip with a zig-zag line. This way of folding a Moebius strip is very closely related to the cut-the-knot logo, omitting the extra knots at the corners.

Isn't it interesting that the cut-the-knot logo can be used to prove K_5 is nonplanar?

--Stuart Anderson

Feeling myself on the cutting edge.

Thank you.

I have a question about the proof on the bipartite graph page.

Why is it true that for any bipartite graph, "no two nodes are connected by 2 edges" (as the proof requires)? I probably do not fully grasp what a bipartite graph is, but from the definitions I find on the web, nothing seems to prevent a vertex in the one set and a vertex in the other to be connected by 2 rather than 1 edge.

Perhpas you don't call that a graph but a 'pseudograph'? But as I understand 'pseudographs' are a subset of all 'graphs'...

To be sure for the 3 utilities problem it makes no sense to have 2 edges between two vertices. However in the proof a general statement about bipartite graphs is made.

Thank you!