Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
add comment

2 Answers 2

up vote 3 down vote accepted

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

share|improve this answer
1  
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
1  
@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
add comment

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

share|improve this answer
    
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
2  
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
1  
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
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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