Kotzig's conjecture

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 ${\displaystyle k}$, where ${\displaystyle k\geq 3}$ is fixed?

More unsolved problems in mathematics

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

The conjecture is stated for ${\displaystyle k\geq 3}$ because ${\displaystyle P_{k}}$-graphs do exist for smaller values of ${\displaystyle k}$. ${\displaystyle P_{1}}$-graphs are precisely the complete graphs. The friendship theorem states that ${\displaystyle P_{2}}$-graphs are precisely the (triangular) windmill graphs (that is, finitely many triangles joined at a common vertex; also known as friendship graphs).