Thread: 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

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).