WorksMathematics
Every -free graph on vertices has a vertex of degree at most
Abstract · v1
We prove that every graph on vertices containing no cycle of length four has a vertex of degree at most . Equivalently, , hence , a value left open in the published tables. In the notation of Erdős, the least integer such that every graph on vertices with minimum degree at least contains a satisfies , while ; the value comes from an explicit -regular -free Cayley graph on vertices, which is also an explicit lower-bound construction for the tabulated value . Hence is not non-decreasing; to our knowledge no with was known before. Erdős's question whether for all sufficiently large (Problem 85 of erdosproblems.com) remains open. The proof combines structural lemmas, valid for every odd , on -free graphs with vertices and minimum degree at least , a symmetry reduction for , and an exhaustive SAT search carried out by two separately written programs.
Review conversation
Reviews are not available for this work yet.