The Erdos-Gyarfas conjecture, in graph theory, states that every graph with minimum degree three contains a simple cycle whose length is a power of two. It was made in 1995 by Paul Erdos and Andras Gyarfas, and Erdos offered a prize of 100 dollars for a proof or 50 dollars for a counterexample. If false, a counterexample would need at least 17 vertices, or at least 30 vertices if cubic, according to computer searches by Gordon Royle and Klas Markstrom. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/
Facts
StatementEvery graph with minimum degree 3 contains a simple cycle whose length is a power of two. 1 Proposed Year Prize StatusErdos offered a prize of 100 dollars for a proof or 50 dollars for a counterexample; unclaimed. 1 Progress Toward ResolutionAny counterexample must have at least 17 vertices (30 if cubic); the conjecture is known true for 3-connected cubic planar graphs and remains open for bipartite cubic graphs. 1 Prize Status
Prize Status (category)Prize Offered, Unclaimed 1 Prize Status (category)Personally-Funded Prize 1 Classification
Resolution Status Connections
In Branch
Source Wikipedia: Erdos-Gyarfas Conjecture
Posed By
Sources
1. Erdos-Gyarfas Conjecture (Wikipedia)
Wikimedia FoundationLead section
made in 1995 by mathematician Paul Erdős and his collaborator András Gyárfás
Lead section, first sentence
every graph with minimum degree 3 contains a simple cycle whose length is a power of two
Lead section, second sentence
offered a prize of $100 for proving the conjecture, or $50 for a counterexample
Lead section, third paragraph
The conjecture remains open for bipartite cubic graphs.
View the Source Wikipedia: Erdos-Gyarfas Conjecture
WikipediaLead section, resolution status
In graph theory, the unproven Erdos-Gyarfas conjecture, made in 1995 by mathematician Paul Erdos and his collaborator Andras Gyarfas, states that every graph with minimum degree 3 contains a simple cycle whose length is a power of two.
- In Branch: Graph Theory, Lead sentence
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.