Five quick responses to the graph theory question. I don't think we need any more on this.........DMD ___________________________ Subject: Re: three questions Date: Tue, 18 Dec 2001 14:14:07 -0800 From: Michael Fisher In answer to Ravenel's question(s): Two complete proofs are given in West's book (Introduction to Graph Theory, 1st ed). One proof appears in Chapter 7 on p. 250. Mike __________________________________ Subject: Nonplanar graphs (was Re: three questions) Date: Tue, 18 Dec 2001 16:21:24 -0600 From: "Martin C. Tangora" >Subject: Nonplanar graphs >Date: Tue, 18 Dec 2001 13:26:49 -0500 (EST) >From: "Douglas C. Ravenel" > >Where can I find an elementary proof that the complete graph on >five vertices and the houses and utilities graph are nonplanar? Right here. Start with V-E+F=2 for every planar graph (Euler). Every face has at least three edges, so 3F leq 2E, which gives E leq 3V - 6. Thus the complete on 5 is nonplanar. The 3x3 is bipartite, so it has no odd cycles, so (if it's planar) every face has at least 4 edges, improving the previous inequality to E leq 2V - 4, so the 3x3 can't be planar. In any text on graph theory, pointless to list them. ______________________________________ Subject: Re: three questions Date: Wed, 19 Dec 2001 07:53:05 +0900 From: Andrzej Kozlowski This follows from Kuratowski's theorem: which says that a graph is planar if and only if it does not contain K5 or K3,3. Actually you only need a weaker statement which is proved in Bollobas "Modern Graph Theory" p.22, Theorem 16. (A proof of the full Kuratowski Theorem may be found in in Harary "Proof techniques in Graph Theory", New York, 1969). Andrzej Kozlowski Toyama International University JAPAN http://platon.c.u-tokyo.ac.jp/andrzej/ ________________________________________ Subject: Re: three questions Date: Tue, 18 Dec 2001 17:35:04 -0800 From: Paul Renteln The houses and utilities graph is officially known as K_{3,3}, the complete bipartite graph on two sets of three vertices each. The quickest proof that K_5 (the complete graph on 5 vertices) and K_{3,3} are non-planar is via Euler's formula. Robin Wilson has a simple presentation in his Introduction to Graph Theory 4th Edition (now out of print, I believe; he has a new one out whose title escapes me, and the proof is probably in there. Of course, the proof is in most graph theory textbooks---see, e.g., West, Introduction to Graph Theory, pp. 255,256). Any plane drawing (no edge crossings) of a planar graph satisfies v-e+f=1+k where v=the number of vertices, e=the number of edges, f=the number of faces (including the infinite face---i.e., the unbounded face), and k=the number of components. If G is connected and simple (no loops and no multiple edges) then (1) e <= 3v-6 and if, in addition, G contains no triangles, then (2) e <= 2v - 4 (Proof: In the first case, each face is bounded by at least 3 edges, so by counting the edges around each face 3f <= 2e In the second case, the inequality becomes 4f <= 2e Now combine with Euler.) Assume K_5 were planar. Then (1) yields 10 < 9. Assume K_{3,3} were planar. Then (2) yields 9 < 8. The converse, of course, is Kuratowski's theorem, which as far as I know does not have as simple a proof. :) Paul Renteln -- ***************************************************** Paul Renteln A man's life in these parts Department of Physics often depends California State University on a mere scrap of information. San Bernardino 5500 University Parkway The Gunslinger San Bernardino, CA 92407 in "Fistfull of Dollars" (909) 880-5402 prenteln@csusb.edu ***************************************************** Subject: Re: three questions Date: Wed, 19 Dec 2001 09:45:16 +0000 From: "Prof. T.Porter" Dear Doug, and everyone else, Nick Gilbert and I left it as an exercise (p. 172 of Knots and Surfaces (O.U.P.,1994)) as it is an easy consequence of Euler's formula, which is proved just before it in the book. I have given elementary proofs in Mathematical Masterclasses for 13 year olds and it worked quite well. The converse statement (that any non-planar graph `contains' K5 or K33) is much harder. We referred to Robin Wilson's book on Graph Theory (1985) for a discussion. An interesting add on is : given a graph \Gamma, find an orientable surface on which \Gamma embeds so that each part of the complement is a disc. I am sure that many readers of these messages know the algorithm but if not it is well worth investigating and makes beautifull doable questions for students. (Nick and I included a brief discussion on p 174-176, but we found it in A.T. White Graphs, groups and Surfaces (Elsevier, 1984). Another source for that area is Gross and Tucker, Topological Graph Theory, (Wiley 1987). The area is of interest as it is closely related to Grothendieck's dessins d'enfants. Classification theorems for graphs embedded on surfaces exist and are quite fun. (A good area for student projects!) Have a Happy Christmas, Tim ************************************************************ Timothy Porter Mathematics Division, School of Informatics, University of Wales Bangor Gwynedd LL57 1UT United Kingdom tel direct: +44 1248 382492 home page: http://www.bangor.ac.uk/~mas013 Mathematics and Knots exhibition: http://www.bangor.ac.uk/ma/CPM/