Comment on Unsolved Problem Number Four
It is certainly true that the references supplied by Yair Caro claim to settle
the conjecture in total, but a closer scrutiny of the Xing and Hu paper reveals
an unfortunate gap in the argument. They show in the paper, and as far as I know
correctly and in my words, that if k>11 then any graph with a (2k-8)-cycle
contains some pair of vertices joined by at least two paths of length (exactly)
k. In other words, no counterexample to the Kotzig conjecture has a cycle of
length exactly 2k-8. They then contrast this with a lemma of Kotzig, a lemma
incidentally cited without proof or reference to any printed proof, which,
again as I can see correctly, claims that: Any P(k)-graph contains a
2n-cycle for a n with 3\leq n\leq k-4.
From this they draw the incorrect conclusion that any P(k) graph has a
(2k-8)-cycle, a contradiction that would prove the Kotzig conjecture for k>11.
The conclusion is incorrect because Kotzig only in essence states that there
exists some 2n cycle in the interval, not that there exists such a cycle for
all n. My reading of this may of course be incorrect, but if it is then it
still remains to fill in Kotzig's part of the proof.
Last modified August 25, 2000, by S.C. Locke.
How to contact me.