Kotzig's conjecture explained

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

Pk

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

k

.Kotzig's conjecture asserts that for

k\ge3

there are no finite

Pk

-graphs with two or more vertices.The conjecture was first formulated by Anton Kotzig in 1974.It has been verified for

k\le20

by Alexandr Kostochka, but remains open in the general case (as of July 2024).

The conjecture is stated for

k\ge3

because

Pk

-graphs do exist for smaller values of

k

.

P1

-graphs are precisely the complete graphs.The friendship theorem states that

P2

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

History

Kotzig's conjecture was first listed as an open problem by Bondy & Murty in 1976, attributed to Kotzig and dated to 1974.Kotzig's first own writing on the conjecture appeared in 1979.He later verified the conjecture for

k\le8

and claimed solution, though unpublished, for

k\le9

.The conjecture is now known to hold for

k\le20

due to work of Alexandr Kostochka. Kostochka stated that his techniques extend to

k\le33

, but a proof of this has not been published.A survey on

Pk

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

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

k\ge12

.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. Kotzig showed that a

Pk

-graph must contain a

2\ell

-cycle for some

\ell\in\{3,...,k-4\}

, 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

k\ge12

a

Pk

-graph must not contain a

(2k-8)

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

Pk

-graphs with

k\ge12

cannot exist.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. It is stated that a general proof for the conjecture seems "out of reach".

Properties of

Pk

-graphs

Pk

-graph on

n

vertices contains precisely

style{n\choose2}

paths of length

k

.

Pk

-graph are connected by a unique

k

-path, each edge is contained in a unique

(k+1)

-cycle. Consequently, the graph has a unique decomposition into edge disjoint

(k+1)

-cycles, and there are no other

(k+1)

-cycles besides these. In particular,

Pk

-graphs are Eulerian.

Pk

-graphs are not bipartite: if

k

is odd and

v,w

are vertices in the same bipartition class, no

k

-path can connect them. Likewise, if

k

is even and

v,w

are vertices in different bipartition classes, no

k

-path can connect them.

Pk

-graphs. A lollipop (sometimes also monocle) is the union of an even

2\ell

-cycle with a path that intersects the cycles in precisely one of its end vertices. The path must be shorter than

k-\ell

as it would otherwise give rise to two

k

-paths with the same end vertices. Therefore, the existence and distribution of lollipops, and more generally, of even cycles, as been studied extensively. It is known that there must exist an even cycle of length

2\ell

for some

\ell\in\{3,...,k-5\}

, and that there cannot exist even cycles of lengths

4

,

2k

,

2k-2

,

2k-4

,

2k-6

or

2k-8

.

Pk

-graph cannot contain a cycle (even or odd) of length at least

\tfrac43k-2

. At the same time, there must exist a cycle of length at least

k+5

. Combining these constraints yield

k\ge21

.

(k+1)

-cycles in a

Pk

-graph must have at least three and at most

k-2

vertices in common. In particular,

G

is 2-connected. Kotzig furthermore claims that any two

(k+1)

-cycles have at least seven vertices in common, though no proof has been published.

ck+1

denote the number of

(k+1)

-cycles in a given

Pk

-graph. Then

ck+1\ge3

. If

k

is even, then

ck+1\ge4

. If

k

is odd, then

ck+1\le\tfrac12(k-1)

. Consequently, the number of edges in a

Pk

-graph (for

k

odd) is bounded, and since

Pk

-graphs are connected, so is the number of vertices.

References

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

Notes and References

  1. Kotzig, A. (1983). Regularly k-path connected graphs. Congressus Numerantium, 40, 137-141.
  2. Kotzig, A. (1979). Selected open problems in graph theory. Graph Theory and Related Topics, 371.
  3. Aigner, M., Ziegler, G.M. (2004). Of friends and politicians. In: Proofs from THE BOOK. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-05412-3_34
  4. Kostochka, A. V. (1988). The nonexistence of certain generalized friendship graphs. In Combinatorics (Eger, 1987) (pp. 341-356). North-Holland, Amsterdam.
  5. Xing, K., & Hu, B. (1994). On Kotzig's conjecture for graphs with a regular path-connectedness. Discrete Mathematics, 135(1-3), 387-393.
  6. Bondy, J. A. (1985). Kotzig's Conjecture on generalized friendship graphs-a survey. In North-Holland Mathematics Studies (Vol. 115, pp. 351-366). North-Holland.
  7. , Problem 4
  8. Book: Bondy. J. A.. Murty. U. S. R.. Graph Theory with Applications. 1976. Macmillan.