Comment on Unsolved Problem Number Four

Kotzig's Conjecture

Roland Häggkvist


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.