Kotzig's conjecture

Each pair of points in the left graph is connected by exactly one path of length 1, and each pair in the right graph is connected by exactly one path 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 .
Unsolved problem in mathematics
Is there a finite graph on at least two vertices in which each pair of distinct vertices is connected by exactly one path of length , where is fixed?

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 -graph if each pair of distinct vertices is connected by exactly one path of length . Kotzig's conjecture asserts that for there are no finite -graphs with two or more vertices. The conjecture was first formulated by Anton Kotzig in 1974. It has been verified for , but remains open in the general case (as of July 2026).

The conjecture is stated for because -graphs do exist for smaller values of . -graphs are precisely the complete graphs. The friendship theorem states that -graphs are precisely the (triangular) windmill graphs (that is, finitely many triangles joined at a common vertex; also known as friendship graphs).