Subject: Re: 5 on graph theory Date: Wed, 19 Dec 2001 15:50:27 -0500 From: Allen Hatcher To: Don Davis There are a couple points in the proof of nonplanarity of the graphs K_5 and K_(3,3) that deserve further comment, it seems to me: 1. It suffices to consider only polygonal embeddings since a topological embedding of a finite graph in the plane can be approximated by a polygonal embedding. This is shown in Bollobas' book by a very simple argument. 2. In order to apply Euler's formula V - E + F = 2 one might think that it is necessary to know that a polygonal embedding of the graph defines a CW structure on the 2--sphere. This is equivalent to knowing the Schoenflies theorem for polygonal simple closed curves in the plane, that such a curve bounds an embedded disk, which is not a trivial theorem. But in fact one can get away with less, just the Jordan curve theorem that such a curve has two complementary components, which is easy to show for polygonal curves. Then interpret the "F" in Euler's formula to be the number of complementary components of the embedded graph, and Bollobas gives a simple proof that V - E + F = 2. Allen Hatcher