Kotzig's conjecture

Statement

Kotzig's conjecture is an unproven assertion in graph theory which states that finite graphs with certain properties do not exist. A graph is a $P_k$-graph if each pair of distinct vertices is connected by exactly one path of length $k$. Kotzig's conjecture asserts that for $k\ge 3$ there are no finite $P_k$-graphs with two or more vertices. The conjecture was first formulated by Anton Kotzig in 1974. It has been verified for $k\le 20$, but remains open in the general case (as of July 2026).