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 <nikl@mathematik.tu-muenchen.de> * 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