HOME

TheInfoList



OR:

Kotzig's conjecture is an unproven assertion in
graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
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 Anton Kotzig (22 October 1919 – 20 April 1991) was a Slovak–Canadian mathematician, expert in statistics, combinatorics and graph theory. A number of his mathematical contributions are named after him. These include the Ringel–Kotzig con ...
in 1974. It has been verified for k\le 20, but remains open in the general case (as of November 2024). The conjecture is stated for k\ge 3 because P_k-graphs do exist for smaller values of k. P_1-graphs are precisely the
complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices i ...
s. The friendship theorem states that P_2-graphs are precisely the (triangular)
windmill graph In the mathematical field of graph theory, the windmill graph is an undirected graph constructed for and by joining copies of the complete graph at a shared universal vertex. That is, it is a 1-clique-sum of these complete graphs. Propert ...
s (that is, finitely many triangles joined at a common vertex; also known as
friendship graph In the mathematical field of graph theory, the friendship graph (or Dutch windmill graph or -fan) is a planar, undirected graph with vertices and edges. The friendship graph can be constructed by joining copies of the cycle graph with a ...
s).


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\le 8 and claimed solution, though unpublished, for k\le 9. The conjecture is now known to hold for k\le 20 due to work of Alexandr Kostochka. Kostochka stated that his techniques extend to k\le 33, but a proof of this has not been published. A survey on P_k-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\ge 12. 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 P_k-graph must contain a 2\ell-cycle for ''some'' \ell\in\, 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\ge 12 a P_k-graph must ''not'' contain a (2k-8)-cycle. Since this is in contradiction to their reading of Kotzig's result, they conclude (incorrectly) that P_k-graphs with k\ge 12 cannot exist. This mistake was first pointed out by Roland Häggkvist in 2000. Kotzig's conjecture is mentioned in
Proofs from THE BOOK ''Proofs from THE BOOK'' is a book of mathematical proofs by Martin Aigner and Günter M. Ziegler. The book is dedicated to the mathematician Paul Erdős, who often referred to "The Book" in which God keeps the most elegant proof of each mathemat ...
in the chapter on the friendship theorem. It is stated that a general proof for the conjecture seems "out of reach".


Properties of P_k-graphs

* A P_k-graph on n vertices contains precisely \textstyle paths of length k. * Since the two end-vertices of an edge in a P_k-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, P_k-graphs are Eulerian. * P_k-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. * Even cycles form important substructures in P_k-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, has been studied extensively. It is known that there must exist an even cycle of length 2\ell for some \ell\in\, and that there cannot exist even cycles of lengths 4, 2k, 2k-2, 2k-4, 2k-6 or 2k-8. * A P_k-graph cannot contain a cycle (even or odd) of length at least \tfrac43 k-2. At the same time, there must exist a cycle of length at least k+5. Combining these constraints yield k\ge 21. * Any two (k+1)-cycles in a P_k-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. * Let c_ denote the number of (k+1)-cycles in a given P_k-graph. Then c_\ge 3. If k is even, then c_\ge 4. If k is odd, then c_\le \tfrac12(k-1). Consequently, the number of edges in a P_k-graph (for k odd) is bounded, and since P_k-graphs are connected, so is the number of vertices.


References

Kotzig, A. (1983). Regularly k-path connected graphs. Congressus Numerantium, 40, 137-141. Kotzig, A. (1979). Selected open problems in graph theory. Graph Theory and Related Topics, 371. 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
Kostochka, A. V. (1988)
The nonexistence of certain generalized friendship graphs
In Combinatorics (Eger, 1987) (pp. 341-356). North-Holland, Amsterdam.
Xing, K., & Hu, B. (1994)
On Kotzig's conjecture for graphs with a regular path-connectedness
Discrete Mathematics, 135(1-3), 387-393.
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.
, Problem 4 {{cite book, last1 = Bondy, first1 = J. A., last2 = Murty, first2 = U. S. R., title = Graph Theory with Applications, url = https://www.iro.umontreal.ca/~hahn/IFT3545/GTWA.pdf, year = 1976, publisher = Macmillan
Unsolved problems in graph theory