# For which $n$ is the graph $C^2_n$ planar?

Let $C_n$ be the simple cycle with $n$ vertices. Let $C^2_n$ be the graph obtained from $C_n$, and includes all the edges $C_n$ plus the edges $\{(u,v) : \mathrm{dist}(u,v) = 2\}$ in $C_n$.

For which $n$ is the graph $C^2_n$ planar and for which is $C^2_n$ not planar?

For instance: $C^2_3$ is planar, $C^2_4$ is planar, $C^2_5$ isn't planar, $C^2_6$ is planar and so on.

Thanks anyway!

-

Approach 1:

Take the vertices of $C^2_n$ labeled $1,2,\dots,n$, with $n$ odd. Examine the cycle $C = (1,3,5,7, \dots, n-4, n-2, n-1, 1)$. The vertex $n$ will lie either inside $C$ or outside $C$, and we can assume it lies inside without loss of generality. Then the two edges $(1,n)$ and $(n,n-2)$ divide $C$ into two interior disjoint subcycles, $S_1 = (1,3,5,7, \dots , n-2 , n, 1)$ and $S_2 = (1, n, n-2, n-1,1)$. Now the vertices $2,4,6, \dots n-3$ form a path disjoint from both $S_1$ and $S_2$, and so, as a group, must lie strictly inside $S_1$, strictly inside $S_2$, or outside $C$.

In the first case, $S_1$ separates $n-1$ from $n-3$. In the second, $S_2$ separates $3$ from $4$, and in the third, $C$ separates $2$ from $n$.

Therefore, $C^2_n$ is not planar for any odd $n > 3$.

Edit: Not sure why I didn't find this configuration immediately, but if you found my first approach unsatisfactory, here is Approach 2:

Take the vertices of $C^2_n$ labeled $1,2,\dots, n$ for $n > 5$. Then, the vertices $1,2,3,4,5,6$ form a $K_{3,3}$ configuration, with bipartitions $1,4,5$ and $2,3,6$. We have the edges $(1,2)$, $(1,3)$, $(4,2)$, $(4,3)$, $(4,6)$, $(5,3)$ and $(5,6)$ explicitly in the graph, so we just need to show that $1$ connects to $6$ and $5$ connects to $2$ in $C_n^2$. Take the path $(6,8,10,\dots,n-1,1)$ as the 'edge' $(6,1)$, and the path $(5,7,9,\dots, n, 2)$ as the 'edge' $(5,2)$. This is a $K_{3,3}$ configuration in $C^2_n$ for every odd $n > 5$, so $C^2_n$ is not planar for any odd $n > 3$.

-
I like this argument, nice and clean. +1 –  EuYu Oct 26 '12 at 4:28
Why $S_1$ and $S_2$ are disjoint, they have a common edges... And for me $S_1$ doesn't separate $n-1$ from $n-3$.. For me now, the proof does not look strong, maybe we can find $K_{3,3}$.. I'm sorry again, but anyway it is useful +1. –  jofisher Oct 26 '12 at 10:28
@jofisher They're interior disjoint. They don't share an interior area. –  EuYu Oct 26 '12 at 18:29
No. The first approach is fine, but for me more comfortable when I see the more stronger proof. Thank you very much! Accept. –  jofisher Oct 26 '12 at 20:22

Certainly $C_n^2$ is planar for $n$ even. Draw $C_n$, draw chords connecting vertex 1 to 3 to 5 to etc. to $n-1$, then draw external arcs connecting 2 to 4 to 6 to etc. to $n$.

$C_7^2$ isn't planar. Label the vertices 1 through 7 in $C_n$. The vertices 1, 4, and 5 are joined to 3, 6, and 7 - the path from 4 to 7 goes through 2, the others are direct links. So there's a $K_{3,3}$, so it's not planar.

I bet the other odd ones ($n\ge7$) all have a $K_{3,3}$.

-
Yep, but the question is about, for which $n$ is also not planar? Probably for some not even $n$ is planar too.. –  jofisher Oct 25 '12 at 22:38
The exact question is, "For which $n$ is the graph $C_n^2$ planar?" So I have answered half of it. I realize it's not a full answer, but it's more knowledge than was asserted in the question, so it's a step forward, no? –  Gerry Myerson Oct 25 '12 at 22:41
Yep, thanks a lot. Sorry for my comments. I just meant that for even it's simple. –  jofisher Oct 25 '12 at 22:46
If it's so simple, why didn't you do it? –  Gerry Myerson Oct 25 '12 at 22:48
I did not pay attention to the description of my question. Most of all I wanted to get a hint for an odd number. Next time, I'll record all the calculations that I have. I'm sorry. –  jofisher Oct 25 '12 at 22:53