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 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 true?

• 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. Commented Oct 22, 2013 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. Commented Oct 22, 2013 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. Commented Oct 22, 2013 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? Commented Oct 23, 2013 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. Commented Oct 23, 2013 at 9:07

1 Answer

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 other question: Does this graph contain at least two Hamiltonian cycles?.