
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 nonplanar?
Please help :(

We note that every vertex of Gn has valency 3, since vertex i has an edge to vertex i1, 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 oddnumbered 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 nonplanarity, recall Kuratowksi's theorem, that if G is a graph with a subgraph "looking like" either K5 or K3,3, then G is nonplanar. 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 n1 and n across the edge joining them, and also contract 2n1 and 2n similarly. You now have a graph "looking like" G(n1). So if G(n1) is nonplanar, 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).