DIMACS TR: 99-28
On Parallel Edges in Cycles
Authors: E. Boros and V. Gurvich
Let $n\leq N$ be positive integers.
We consider the problem of finding an $n$-cycle with no parallel edges in a perfect $N$-gon in the Euclidian plane.
We prove that there exist no such $n$-cycle if and only if $N=n$ and even.
And we show by construction that for every other pair
$(N,n)$, $N \geq n \geq 3$, such an $n$-cycle exists.
Paper Available at:
DIMACS Home Page