# Discrete Maths

1. May 16, 2006

### Natasha1

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. May 16, 2006

### 0rthodontist

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?

3. May 16, 2006

### Natasha1

I'm very new to all this. I just picked up a textbook and I'm trying to teach myself.

Seems quite complex

4. May 16, 2006

### 0rthodontist

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.