Status
On this page
Status
Topics
Status
On this page
Status
Topics
We call a graph -balanced (or -almost-regular) if the maximum degree is at most times the minimum degree.
Let and and be sufficiently large. If is a graph on vertices with at least edges, then must contain a -balanced subgraph on vertices with at least edges?
Source: erdosproblems.com/1077
An accepted solution exists. The statement is false.
DISPROVED (LEAN), the site's label, which describes the Statement as printed. The witness is the one the site's commentary names, a complete bipartite graph whose smaller side has about vertices, recomputed here in the Current assessment: for , every and every , the graph with has at least edges for large , and every -balanced subgraph of it with an edge has at most vertices, so no -balanced subgraph on more than vertices has any edge. As a universal statement over and the Statement is therefore false; for this witness gives nothing and the page decides nothing. The failure holds for every , not only at boundary values, and the exponent is the poser's explicit print, so the curator's guess at the intended question is a variant (Formulation) and not a correction. A Lean file refutes the collection's formal statement with the same family at , and with it the printed wording, which implies that statement; the corpus built the file and audited its statement (Formalization). The claim pages record the complete bipartite witness of 28 December 2025 (JunGao), the clique counterexample of 24 December 2025 (clique counterexample) and the Lean file (Lean file). JunGao's witness carries the site's acceptance, since the site's label and commentary credit JunGao and the complete bipartite graph; the Lean file's acceptance rests on the corpus's build and statement audit; the clique construction, which neither the site nor a build credits, is claimed.