# the “compact good array” in a “good $N^+$-cycle”

We use $N^+$ to denote the set of positive integers.For any finite array $A:(a_1,b_1),...,(a_k,b_k)$,where every $(a_i,b_i)\in N^+\times N^+$,we call $A$ is good if for every $i\in \{a_1,b_1,...,a_k,b_k\}$,$i$ appears exactly two times in $a_1,b_1,...,a_k,b_k$.For example,$A_1:(1,1)$,$A_2:(1,2),(1,2)$ and $A_3:(1,2),(2,1)$ are all good,but $A_4:(1,2),(1,3)$ is not good.Moreover we call a good array $A$ is compact if there does not exist a proper sub-array of $A$ which is good.For example,$A:(1,2),(3,4),(2,1),(4,3)$ is good but not compact,because $(1,2),(2,1)$ is a proper sub-array of $A$ which is also good.

We define a good $N^+$-cycle $C=a_1$-$a_2$-...-$a_n$-$a_1$ is a "diamond necklace" such that every "diamond" $a_i$ is a positive integer and appears exactly two times in $a_1,a_2,...,a_n$.For example,$1$-$2$-$3$-$1$-$2$-$3$-$1$ is a good $N^+$-cycle.I conjecture that for every $N^+$-cycle $C=a_1$-$a_2$-...-$a_n$-$a_1$,there must exist $1\leq i_1<i_2<...i_k\leq n$ such that

$(1）i_2-i_1\geq 2,...,i_k-i_{k-1}\geq 2,i_1+n-i_k\geq 2$;

$(2)(a_{i_1},a_{i_2-1}),(a_{i_2},a_{i_3-1}）...,(a_{i_{k-1}},a_{i_k-1}),(a_{i_k},a_{i_1-1})$$(when i_1=1,let a_{i_1-1}=a_0=a_n$$)$ is a compact good array.

$($Remark:just like cut the "diamond necklace" into $k$ paragraphs:$(a_{i_1}$-$a_{i_1+1}$-...-$a_{i_2-1})$-$(a_{i_2}$-$a_{i_2+1}$-...-$a_{i_3-1})$-...-$(a_{i_{k-1}}$-$a_{i_{k-1}+1}$-...-$a_{i_k-1})$-$(a_{i_k}$-$a_{i_k+1}$-...-$a_{i_1-1})$-$)$

Is it ture?

-
Each good array is partitioned into several compact ones. Now for your cycle, the array $(a_1,a_2),(a_3,a_4),\dots$ is good. Now choose any compact array in its partition; the indices of the second elements in its pairs are what you need. –  Ilya Bogdanov Oct 22 '13 at 7:02
Hello，Ilya Bogdanov.What you said is not ture.For example,$(1,2),(2,3),(3,1)$ is a compact good array,but$(2,2),(3,3),(1,1)$ is good but not compact. –  user40096 Oct 22 '13 at 11:24
Once more. The good array $(a_1,a_2),(a_3,a_4),\dots$ is GOOD. So it can be PARTITIONED into good compact ones (in your second example --- into three one-element ones); in fact, every good array can be partitioned in this way. An arbitrary compact array in this partition --- alone --- is what you want. –  Ilya Bogdanov Oct 22 '13 at 13:27
Ok,suppose the good cycle is $1$-$2$-$4$-$5$-$2$-$3$-$5$-$6$-$3$-$1$-$6$-$4$-$1$,as you said,$(1,2),(4,5),(2,3),(5,6),(3,1),(6,4)$ is good,then partitioned it into good compact ones:$(1,2),(2,3),(3,1)$ and $(4,5),(5,6),(6,4)$,what about then? –  user40096 Oct 23 '13 at 0:31
Oh, sorry. Finally you were managed to explain the trouble to (stupid) myself, thanks; now I see that the array is rearranged. –  Ilya Bogdanov Oct 23 '13 at 9:07

Let G be a simple graph which is a $2n$-cycle equipped with $n$ chords such that $G$ is $3$-regular,in other words,the set of the $n$ chords is a perfect matching of $G$(that is,every vertex of $G$ is matched).Then there must exist at least two different $2n$-cycles in $G$.