Results 1 to 2 of 2

Math Help - Discrete Maths

  1. #1
    Senior Member
    Joined
    Apr 2006
    Posts
    290

    Discrete Maths

    Gn (n >= 2) is a graph representing the vertices and edges of a regular 2n sided polygon, with additional edges formed by the diagonals for each vertex joined to the vertex opposite i.e. vertex 1 is joined to n+1, vertex 2 to n+2 and so on, vertex n to 2n.

    1) Show that G3 is isomorphic to K3,3?

    2) State (with reason) a value of n for which Gn is planar. Explaining why for all values greater than this value of n, Gn will be non-planar?

    Please help
    Last edited by Natasha1; May 22nd 2006 at 05:22 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Jun 2005
    Posts
    295
    Awards
    1
    We note that every vertex of Gn has valency 3, since vertex i has an edge to vertex i-1, i+1 and i+n (all taken modulo 2n). If n is 3, then taking vertex numbers modulo 6, we see that i is linked to i+1,i+3 and i+5; that is, to all three vertices with the opposite parity to i. So each even numbered vertex is linked to all odd-numbered vertices and vice versa. Hence G6 has a bipartition (even and odd) and each vertex is each class is linked to all the vertices in the other class. That is, it is complete bipartite.

    For the non-planarity, recall Kuratowksi's theorem, that if G is a graph with a subgraph "looking like" either K5 or K3,3, then G is non-planar. Exactly what "looking like" means in this theorem is a little tricky, since there are two, different but confusingly similar ways of saying it.

    However in this case it's not too hard. Take Gn with n>3 and contract vertices n-1 and n across the edge joining them, and also contract 2n-1 and 2n similarly. You now have a graph "looking like" G(n-1). So if G(n-1) is non-planar, so is Gn. You have to start your induction proof somewhere: I leave it as an exercise to decide exactly where (ie to decide which Gn are planar for small values of n).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Discrete Maths
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: January 18th 2010, 06:58 AM
  2. discrete maths
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 21st 2009, 07:44 AM
  3. Discrete set maths
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: August 27th 2009, 12:40 AM
  4. help me in discrete maths
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 14th 2008, 06:50 AM
  5. Discrete maths
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: August 11th 2006, 08:19 AM

Search Tags


/mathhelpforum @mathhelpforum