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.

Give some clue please!

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

  • 1
    $\begingroup$ I like this argument, nice and clean. +1 $\endgroup$ – EuYu Oct 26 '12 at 4:28
  • $\begingroup$ 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. $\endgroup$ – brainail Oct 26 '12 at 10:28
  • 1
    $\begingroup$ @jofisher They're interior disjoint. They don't share an interior area. $\endgroup$ – EuYu Oct 26 '12 at 18:29
  • $\begingroup$ No. The first approach is fine, but for me more comfortable when I see the more stronger proof. Thank you very much! Accept. $\endgroup$ – brainail 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}$.

  • $\begingroup$ Yep, but the question is about, for which $n$ is also not planar? Probably for some not even $n$ is planar too.. $\endgroup$ – brainail Oct 25 '12 at 22:38
  • 2
    $\begingroup$ 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? $\endgroup$ – Gerry Myerson Oct 25 '12 at 22:41
  • $\begingroup$ Yep, thanks a lot. Sorry for my comments. I just meant that for even it's simple. $\endgroup$ – brainail Oct 25 '12 at 22:46
  • $\begingroup$ If it's so simple, why didn't you do it? $\endgroup$ – Gerry Myerson Oct 25 '12 at 22:48
  • 1
    $\begingroup$ 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. $\endgroup$ – brainail Oct 25 '12 at 22:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.