Kotzig's unique $k$-path conjecture

Status partial high confidence

Kotzig's conjecture asserts that for k ≥ 3 no finite graph (called a P_k-graph or k-graph) exists in which every pair of vertices is connected by exactly one path of length k. The conjecture has been verified for all k ≤ 20 by Kostochka (1988), who also claimed—without publishing a proof—that his techniques extend to k ≤ 33. An earlier claimed proof for k ≥ 12 by Xing and Hu (1994) was identified as fatally flawed by Häggkvist in 2000. As of July 2026 the conjecture remains open in the general case.

Cited literature (2)

• partial The nonexistence of certain generalized friendship graphs (1988)
  Kostochka, A.V. · Combinatorics (Eger, 1987), Colloq. Math. Soc. János Bolyai 52, North-Holland, pp. 341–356

  Proves that no P_k-graph with at least two vertices exists for all k ≤ 20, and claims (without a published proof) an extension to k ≤ 33.

• partial On Kotzig's conjecture for graphs with a regular path-connectedness (1994)
  Xing, K.; Hu, B. · Discrete Mathematics 135(1–3), 387–393 · doi:10.1016/0012-365X(93)E0106-E

  Claimed to prove the conjecture for k ≥ 12, but the proof was subsequently found to be flawed (error identified by Häggkvist in 2000).

Reviewer notes. The Wikipedia article on Kotzig's conjecture (verified via WebFetch, current as of July 2026) is the primary source for the k ≤ 20 status. The case k = 2 is exactly the Friendship Theorem (Theorem 3.1 in the book), which states that the only graphs where every pair of vertices has a unique path of length 2 are the windmill graphs. The arXiv paper 2510.01949 titled 'On Kotzig's conjecture in random graphs' addresses a different Kotzig conjecture concerning Hamilton cycle decompositions of complete graphs, not the unique-k-path conjecture. The Xing & Hu paper listed in since_posted is included for completeness as it determined the research landscape post-2000, even though its main claim was retracted. The ScienceDirect URL for the Xing & Hu paper was found in search results but not independently verified via WebFetch; only the Kostochka (1988) result and the Wikipedia summary were independently confirmed.

Auto-reviewed 2026-09-10 with claude-sonnet-4-6 (web search enabled).