Status
On this page
Status
Topics
Status
On this page
Status
Topics
Is it true that, for every bipartite graph , there exists some and such that
Must be rational?
Is it true that, for every bipartite graph with at least two edges, there exists some and such that
Must be rational?
Source: erdosproblems.com/713
No claim settles this problem.
Open. The site labels the problem OPEN, with a prize (snapshot accessed 2026-09-04), a label that describes the corrected Statement. Neither question of the corrected Statement has a claim page, so the frontmatter standing derived from the claim pages is open with no claim. The site's wording fails at graphs with at most one edge, as the Notes record.
The site's wording admits every bipartite graph, and its first question fails at the smallest ones. A graph with one edge, together with any isolated vertices, has for , since copies need not be induced and a host avoiding then has no edges; so for every and the ratio is eventually and does not tend to . A graph with no edges is contained in every host with at least vertices, so its extremal number is undefined for large . These checks are the corpus's own. The failures lie at the smallest sizes of the forbidden graph, the graphs with at most one edge, and at these sizes no graph can meet the conclusion. The next size has none: a bipartite graph with two edges is a path with two edges or two disjoint edges, with isolated vertices added, and for large its extremal number is (a perfect or near-perfect matching) or (a star), so with .
The change inserts "with at least two edges" after "every bipartite graph "; nothing else changes. It is the corpus's own correction, excluding exactly the forbidden graphs too small for the conclusion to hold. Erdős's own statement of the conjecture with Simonovits ([Er67d], p. 119, display (8); library card) does not fail at the graphs with one edge: it is written for the least number of edges that forces , which is , with for some , and a graph with one edge has for large . The failure there comes from the site's restatement in terms of with . The formal-conjectures statement file adopts the same two-edge condition.