Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Discrete Maths

  1. May 16, 2006 #1
    I wondered if someone could help me with the following problem.

    Gn (n >= 2) is a graph representing the vertices abd 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) How can I show that G3 is isomorphic to K3,3?

    2) How can I 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?

  2. jcsd
  3. May 16, 2006 #2


    User Avatar
    Science Advisor

    In 1. first you have to decide which vertices in G3 map to which vertices in K3, 3. (Draw a picture of K3, 3 and of G3) Then verify that for the mapping you decided on, the edges map correctly.

    In 2. can you find a subgraph homeomorphic to K3, 3 in G4?
  4. May 16, 2006 #3
    I'm very new to all this. I just picked up a textbook and I'm trying to teach myself.

    Seems quite complex
  5. May 16, 2006 #4


    User Avatar
    Science Advisor

    You need to know:
    what an isomorphism is
    what K3, 3 is
    the theorem relating K3, 3 to nonplanar graphs
    what a homeomorphism is

    If you know these things it's not a complex problem.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook