1
$\begingroup$

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!

2 Answers 2

3

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

  • 0
    No. The first approach is fine, but for me more comfortable when I see the more stronger proof. Thank you very much! Accept.2012-10-26
1

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

  • 0
    Hm.. Ok. I'm not sure but I will think about your suggestion.2012-10-26