graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

, the unproven Erdős–Gyárfás conjecture, made in 1995 by the prolific mathematician

Paul Erdős Paul Erdős ( hu, Erdős Pál ; 26 March 1913 – 20 September 1996) was a Hungarian mathematician. He was one of the most prolific mathematicians and producers of mathematical conjectures of the 20th century. pursued and proposed problems in ...

and his collaborator

András Gyárfás András Gyárfás (born 1945) is a Hungarian mathematician who specializes in the study of graph theory. He is famous for two conjectures: * Together with Paul Erdős he conjectured what is now called the Erdős–Gyárfás conjecture which sta ...

, states that every

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...

with minimum

degree Degree may refer to: As a unit of measurement * Degree (angle), a unit of angle measurement ** Degree of geographical latitude ** Degree of geographical longitude * Degree symbol (°), a notation used in science, engineering, and mathematics ...

3 contains a

simple cycle In graph theory, a cycle in a graph is a non-empty trail in which only the first and last vertices are equal. A directed cycle in a directed graph is a non-empty directed trail in which only the first and last vertices are equal. A graph witho ...

whose length is a

power of two A power of two is a number of the form where is an integer, that is, the result of exponentiation with number two as the base and integer as the exponent. In a context where only integers are considered, is restricted to non-negative ...

. Erdős offered a prize of $100 for proving the conjecture, or $50 for a counterexample; it is one of many conjectures of Erdős. If the conjecture is false, a counterexample would take the form of a graph with minimum degree three having no power-of-two cycles. It is known through computer searches of

Gordon Royle Gordon F. Royle is a professor at the School of Mathematics and Statistics at The University of Western Australia. Royle is the co-author (with Chris Godsil) of the book ''Algebraic Graph Theory'' (Springer Verlag, 2001, ). Royle is also known ...

and Klas Markström that any counterexample must have at least 17 vertices, and any

cubic Cubic may refer to: Science and mathematics * Cube (algebra), "cubic" measurement * Cube, a three-dimensional solid object bounded by six square faces, facets or sides, with three meeting at each vertex ** Cubic crystal system, a crystal system w ...

counterexample must have at least 30 vertices. Markström's searches found four graphs on 24 vertices in which the only power-of-two cycles have 16 vertices. One of these four graphs is

planar Planar is an adjective meaning "relating to a plane (geometry)". Planar may also refer to: Science and technology * Planar (computer graphics), computer graphics pixel information from several bitplanes * Planar (transmission line technologies), ...

; however, the Erdős–Gyárfás conjecture is now known to be true for the special case of 3-connected cubic planar graphs Weaker results relating the degree of a graph to unavoidable sets of cycle lengths are known: there is a set ''S'' of lengths, with , ''S'', = O(''n''^0.99), such that every graph with average degree ten or more contains a cycle with its length in ''S'' , and every graph whose average degree is exponential in the

iterated logarithm In computer science, the iterated logarithm of n, written n (usually read "log star"), is the number of times the logarithm function must be iteratively applied before the result is less than or equal to 1. The simplest formal definition i ...

of ''n'' necessarily contains a cycle whose length is a power of two . The conjecture is also known to be true for planar

claw-free graph In graph theory, an area of mathematics, a claw-free graph is a graph that does not have a claw as an induced subgraph. A claw is another name for the complete bipartite graph ''K''1,3 (that is, a star graph comprising three edges, three leaves, ...

s and for graphs that avoid large induced

star A star is an astronomical object comprising a luminous spheroid of plasma (physics), plasma held together by its gravity. The List of nearest stars and brown dwarfs, nearest star to Earth is the Sun. Many other stars are visible to the naked ...

s and satisfy additional constraints on their degrees .

References

*. *. *. * *. *.

External links

*Exoo, Geoffrey
Graphs Without Cycles of Specified Lengths
*West, Douglas B.

' {{DEFAULTSORT:Erdos-Gyarfas conjecture Conjectures Unsolved problems in graph theory Gyarfas conjecture