Erdős Problem #73
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (not automatically the live result).
Subject areas: graph theory.
Read this status correctly
The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.
The question in plain language
An independent set in a graph contains no adjacent pair of vertices. Every bipartite graph has an independent set of at least half its vertices, namely the larger side of its two-coloring. Erdős #73 asks whether a graph is almost bipartite if every subgraph has an independent set of size at least half its vertices, apart from a fixed additive defect.
More precisely, for a fixed \(k\ge0\), assume every finite subgraph \(H\) on \(n\) vertices satisfies
Must deleting at most \(f(k)\) vertices make the whole graph bipartite? The constant must depend only on \(k\), not on the number of vertices.
A small example
An odd cycle \(C_{2t+1}\) has independence number exactly \(t\), because one cannot choose adjacent vertices. For \(k=0\), its required lower bound would be \(t+1/2\), impossible. Thus any graph satisfying the \(k=0\) condition contains no odd cycle and is bipartite. This elementary case is a complete proof only when \(k=0\).
For \(k>0\) an odd cycle may fit within the allowed defect. Counting odd cycles individually does not establish that all obstructions are contained in a bounded set of vertices.
What is known
The problem is PROVED by Bruce Reed. The primary publication is Mangoes and Blueberries, Combinatorica 19 (1999), pages 267–296, DOI 10.1007/s004930050056. Its bibliographic entry is recorded by the publisher and the Combinatorica volume index. The maintained Erdős problem explicitly attributes the general statement to Reed.
An older graph-problem list described an unpublished solution. The existence of Reed's 1999 article corrects the historical provenance, but its full text was not available for a theorem-by-theorem check in this pass. In particular, GCL has not extracted an explicit bound on \(f(k)\) or certified whether additional finiteness conventions are present in the primary theorem. The source classification is not a claim that GCL has reconstructed the deep proof.
GCL's current state
The original issue is ERDOS-CATALOGUE-0073-S01. The primary publication has been located, the catalogue theorem compared with the problem's quantifiers, and the \(k=0\) proof checked. This is a pending editorial draft with an explicit full-primary-text access exception.
The original GitHub issue now contains the authenticated RESULT/1 source report. This does not imply independent mathematical review or editorial admission.
What remains
A bounded source-fidelity task is to inspect Reed's printed proof, identify the exact finite-versus-infinite graph hypothesis, and extract or bound \(f(k)\). A separate formal exercise establishes \(\alpha(C_{2t+1})=t\) and “a graph is bipartite if and only if it contains no odd cycle.” Neither exercise resolves the general \(k>0\) case without Reed's deeper structural machinery.
Sources and claim boundaries
- Reed, Mangoes and Blueberries, Combinatorica 19 (1999), 267–296, published primary record; full proof not independently page-audited.
- Maintained Erdős #73, directly attributed to Reed.
- GCL original source issue #1342.
No novel theorem, complete Reed proof certification or editorial admission is claimed.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1342 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
- Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.