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 András 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.
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
In graph theory, the unproven Erdős-Gyárfás conjecture, made in 1995 by mathematician Paul Erdős and his collaborator András Gyárfás, 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.