Kotzig's conjecture

Kotzig's conjecture is an unproven assertion in graph theory which states that finite graphs with certain properties do not exist.

-graph if each pair of distinct vertices is connected by exactly one path of length

The conjecture was first formulated by Anton Kotzig in 1974.

,[1] but remains open in the general case (as of November 2024).

-graphs are precisely the (triangular) windmill graphs (that is, finitely many triangles joined at a common vertex; also known as friendship graphs).

Kotzig's conjecture was first listed as an open problem by Bondy & Murty in 1976,[3] attributed to Kotzig and dated to 1974.

[2] Kotzig's first own writing on the conjecture appeared in 1979.

due to work of Alexandr Kostochka.

[1] Kostochka stated that his techniques extend to

-graphs was written by John A. Bondy, including proofs for many statements previously made by Kotzig without written proof.

[7] In 1990 Xing & Hu claimed a proof of Kotzig's conjecture for

[8] This seemed to resolve the conjecture at the time, and still today leads many to believe that the problem is settled.

However, Xing and Hu's proof relied on a misunderstanding of a statement proven by Kotzig.

,[5] which Xing and Hu used in the form that cycles of all these lengths must exist.

In their paper Xing and Hu show that for

Since this is in contradiction to their reading of Kotzig's result, they conclude (incorrectly) that

This mistake was first pointed out by Roland Häggkvist in 2000.

Kotzig's conjecture is mentioned in Proofs from THE BOOK in the chapter on the friendship theorem.

[6] It is stated that a general proof for the conjecture seems "out of reach".

Each pair of points in the first graph is connected by exactly one path of length 1, and each pair in the second is connected by one of length 2. These are the cases and respectively, but no graphs with have been found. It is known that if another does exist, it must be where . [ 1 ]