1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: 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