MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 0 down vote accepted

The conjecture is right.It is equivalent to the claim below:

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

The proof is given by Tony Huynh,see my another question:an interesting conjecture about even cycle.

share|cite|improve this answer

Your Answer


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.