From: nikl+sm000713@pchelwig1.mathematik.tu-muenchen.de (Gerhard Niklasch) Newsgroups: sci.math Subject: Re: Graph Theory--Genus Problems Date: 21 Nov 1998 18:24:47 GMT In article <72vbki$naq$1@scapa.cs.ualberta.ca>, kiwon@scapa.cs.ualberta.ca (Ki-Won Lee) writes: |> I have a couple of questions pertaining to the above that have stumped me |> and I'd appreciate some help in this: |> |> 1. The surface of a torus can be regarded as a rectangle in which opposite |> edges are identified (see fig. below). Using this representation, show |> that Petersen graph has genus 1. Most often the Petersen graph is drawn as a plane picture with 5 crossings, as follows (display this with a non-proportional font): *---------------* / \ / \ / \ / \ / \ / \ / *. .* \ / | `-_-' | \ / _+-~ ~-+_ \ *-------*=~--+---+--~=*-------* `. \ / ,' `. V ,' `. * ,' `. | ,' `. | ,' `. | ,' `.|,' * Turning the affair inside out and drawing the rectangle around it, we get: +-----------------------------------------+ | ,' `. ,' | | ,' `. ,' | |,' * | | | | | | | | | '| | * ,' | | ,' `. / | | ,' `. / | |-----*_ ,' `. _*-----| | / ~-_ ,' `. _-~ | | ,' ~* *~ | |,' \ / | | \ / | | \ / ,'| | \ / ,' | | *-------* ,' | | ,' `. ,' | | ,' `. ,' | | * *~ | | ,' \ / | | ,' `. ,' | +-----------------------------------------+ Now add suitable labels pairing up the half and third edges which cross the boundary of the rectangle to convince yourself that we have indeed a drawing of the Petersen graph on a torus, without crossings. Can you show that the graph isn't planar (i.e. that its genus is nonzero)? |> 2. Given Theorem: The genus of a graph does not exceed the crossing number. |> Let genus of graph be "g". |> i) Using the above theorem, prove that there is no value of n for which |> g(K_n) = 7. [...] |> ii)What is the next integer that is not the genus of any complete graph? [...] So, what is g(K_n) for n = 4, 5, 6, 7, 8, 9, 10? Note that since K_n contains K_(n-1) as a subgraph, the genus of K_n is at least as large as that of K_(n-1), for every positive n. -- * Gerhard Niklasch * spam totally unwelcome * http://hasse.mathematik.tu-muenchen.de/~nikl/ ******* all browsers welcome * This .signature now fits into 3 lines and 77 columns * newsreaders welcome