Erdős–Gyárfás conjecture

The Erdős–Gyárfás conjecture states that every finite graph with minimum degree at least three contains a cycle whose length is a power of two.

Connect

Graph (discrete mathematics): A graph is a mathematical structure consisting of vertices joined by edges. The conjecture concerns finite graphs and imposes a condition on every vertex.
Girth (graph theory): The girth of a graph is the length of its shortest cycle. Girth bounds can force short cycles, though they do not by themselves guarantee a power-of-two length.
Paul Erdős: Paul Erdős was a Hungarian mathematician whose work shaped combinatorics and graph theory. He co-formulated the problem with András Gyárfás.
Cubic graph: A cubic graph is a graph in which every vertex has degree three. Cubic graphs are the boundary case for the conjecture's minimum-degree hypothesis.
Vertex degree: The degree of a vertex is the number of edges incident to it. Minimum degree three is the hypothesis that drives the conjecture.
Breadth-first search: Breadth-first search explores a graph in layers of increasing distance from a starting vertex. Layering arguments help convert degree conditions into information about cycles.
András Gyárfás: András Gyárfás is a Hungarian mathematician known for work in graph theory and combinatorics. He co-authored the paper that introduced the conjecture.
Complete graph: A complete graph has an edge between every pair of distinct vertices. Its abundant cycles make the required power-of-two length easy to find.
Cycle (graph theory): A cycle is a closed path in a graph with no repeated vertices except its start and end. The conjecture asserts the existence of a cycle of a specified length.
Moore bound: The Moore bound gives a lower bound on the number of vertices in a graph with specified degree and girth. It captures the tension between large minimum degree and avoiding short cycles.