# P3012: Erdős's variant on almost-bipartite subgraphs of infinite-chromatic graphs

- ID: `P3012`
- Reference: `erdos-problem-74`
- Page: https://theoremdb.org/statements/P3012
- Record maturity: Reviewed problem with recorded work

## Problem

Erdős Problem 74: For a simple graph $G$ and a natural number $n$, let the edge distance to bipartite of a subgraph $A$ of $G$ be the minimum number of edges that must be deleted from $A$ to obtain a bipartite graph. Let the maximum subgraph edge distance to bipartite of $G$ at $n$, denoted $b_G(n)$, be the supremum of the edge distances to bipartite over all induced subgraphs of $G$ on exactly $n$ vertices (this supremum is finite because deleting all edges of an $n$-vertex graph, at most $\binom{n}{2}$, always yields a bipartite graph). Does there exist a graph $G$ with infinite chromatic number such that for every natural number $n$, we have $b_G(n) \leq \sqrt{n}$?

### Context

This is a specific variant of a problem posed by Erdős, Hajnal, and Szemerédi (1982) concerning how close to bipartite the finite subgraphs of an infinite-chromatic graph can be. The original problem asked whether for every function $f(n) \to \infty$, there exists a graph of infinite chromatic number whose $n$-vertex subgraphs can all be made bipartite by deleting at most $f(n)$ edges. This variant asks whether the specific bound $\sqrt{n}$ suffices.

### Problem setup

- **Definition (For a simple graph $A$, the edge distance to bipartite).** For a simple graph $A$, the edge distance to bipartite is the minimum cardinality of a set of edges whose removal from $A$ yields a bipartite graph.
- **Definition (For a simple graph $G$ and a natural number $n$, the maximum subgraph edge distance to bipartite $b_G(n)$).** For a simple graph $G$ and a natural number $n$, the maximum subgraph edge distance to bipartite $b_G(n)$ is the maximum, over all induced subgraphs of $G$ with exactly $n$ vertices, of the edge distance to bipartite of that subgraph.
- **Remark.** This is a specific variant of a problem posed by Erdős, Hajnal, and Szemerédi (1982) concerning how close to bipartite the finite subgraphs of an infinite-chromatic graph can be. The original problem asked whether for every function $f(n) \to \infty$, there exists a graph of infinite chromatic number whose $n$-vertex subgraphs can all be made bipartite by deleting at most $f(n)$ edges. This variant asks whether the specific bound $\sqrt{n}$ suffices.

### What counts as a solution

- Give a rigorous proof or counterexample that completely resolves this statement: Erdős Problem 74: For a simple graph $G$ and a natural number $n$, let the edge distance to bipartite of a subgraph $A$ of $G$ be the minimum number of edges that must be deleted from $A$ to obtain a bipartite graph. Let the maximum subgraph edge distance to bipartite of $G$ at $n$, denoted $b_G(n)$, be the supremum of the edge distances to bipartite over all induced subgraphs of $G$ on exactly $n$ vertices (this supremum is finite because deleting all edges of an $n$-vertex graph, at most $\binom{n}{2}$, always yields a bipartite graph). Does there exist a graph $G$ with infinite chromatic number such that for every natural number $n$, we have $b_G(n) \leq \sqrt{n}$?

## Status

OPEN as of 2026-07-31. The maintained Erdős Problems database at commit 8138974387d9030542daabe67faaa33eff9356f8 lists Problem 74 as open. The unresolved remainder is the full displayed statement. Give a rigorous proof or counterexample that completely resolves this statement: Erdős Problem 74: For a simple graph $G$ and a natural number $n$, let the edge distance to bipartite of a subgraph $A$ of $G$ be the minimum number of edges that must be deleted from $A$ to obtain a bipartite graph. Let the maximum subgraph edge distance to bipartite of $G$ at $n$, denoted $b_G(n)$, be the supremum of the edge distances to bipartite over all induced subgraphs of $G$ on exactly $n$ vertices (this supremum is finite because deleting all edges of an $n$-vertex graph, at most $\binom{n}{2}$, always yields a bipartite graph). Does there exist a graph $G$ with infinite chromatic number such that for every natural number $n$, we have $b_G(n) \leq \sqrt{n}$? [1](#reference-1)

## Work

### Evidence for the current status

**Claim 1 (Current status and unresolved remainder).** OPEN as of 2026-07-31. The maintained Erdős Problems database at commit 8138974387d9030542daabe67faaa33eff9356f8 lists Problem 74 as open. The unresolved remainder is the full displayed statement. Give a rigorous proof or counterexample that completely resolves this statement: Erdős Problem 74: For a simple graph $G$ and a natural number $n$, let the edge distance to bipartite of a subgraph $A$ of $G$ be the minimum number of edges that must be deleted from $A$ to obtain a bipartite graph. Let the maximum subgraph edge distance to bipartite of $G$ at $n$, denoted $b_G(n)$, be the supremum of the edge distances to bipartite over all induced subgraphs of $G$ on exactly $n$ vertices (this supremum is finite because deleting all edges of an $n$-vertex graph, at most $\binom{n}{2}$, always yields a bipartite graph). Does there exist a graph $G$ with infinite chromatic number such that for every natural number $n$, we have $b_G(n) \leq \sqrt{n}$?

OPEN as of 2026-07-31. The maintained Erdős Problems database at commit 8138974387d9030542daabe67faaa33eff9356f8 lists Problem 74 as open. The unresolved remainder is the full displayed statement.

A complete resolution must satisfy this condition: Give a rigorous proof or counterexample that completely resolves this statement: Erdős Problem 74: For a simple graph $G$ and a natural number $n$, let the edge distance to bipartite of a subgraph $A$ of $G$ be the minimum number of edges that must be deleted from $A$ to obtain a bipartite graph. Let the maximum subgraph edge distance to bipartite of $G$ at $n$, denoted $b_G(n)$, be the supremum of the edge distances to bipartite over all induced subgraphs of $G$ on exactly $n$ vertices (this supremum is finite because deleting all edges of an $n$-vertex graph, at most $\binom{n}{2}$, always yields a bipartite graph). Does there exist a graph $G$ with infinite chromatic number such that for every natural number $n$, we have $b_G(n) \leq \sqrt{n}$?

### Background and intake notes

- Original intake status: OPEN as of 2026-07-31. The maintained Erdős Problems database at commit 8138974387d9030542daabe67faaa33eff9356f8 lists Problem 74 as open. The unresolved remainder is the full displayed statement.
- The maintained database entry for Erdős Problem 74 was open at commit 8138974387d9030542daabe67faaa33eff9356f8.
- The pinned Formal Conjectures declaration was matched by problem number and source locator.
- The controlled TheoremDB source corpus was checked for an already published record with the same slug.

### Open directions

- **Route 1** (reported): Give a rigorous proof or counterexample that completely resolves this statement: Erdős Problem 74: For a simple graph $G$ and a natural number $n$, let the edge distance to bipartite of a subgraph $A$ of $G$ be the minimum number of edges that must be deleted from $A$ to obtain a bipartite graph. Let the maximum subgraph edge distance to bipartite of $G$ at $n$, denoted $b_G(n)$, be the supremum of the edge distances to bipartite over all induced subgraphs of $G$ on exactly $n$ vertices (this supremum is finite because deleting all edges of an $n$-vertex graph, at most $\binom{n}{2}$, always yields a bipartite graph). Does there exist a graph $G$ with infinite chromatic number such that for every natural number $n$, we have $b_G(n) \leq \sqrt{n}$? [1](#reference-1)

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `erdos-problem-74`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1. <a id="reference-1"></a>Erdős Problems database, Problem 74, maintained status record. Erdős Problems record 74, checked 2026-08-01. Problem 74; status field and linked bibliography https://www.erdosproblems.com/74
   - Also cited at Problem 74; status snapshot 8138974387d9030542daabe67faaa33eff9356f8
   - Also cited at See dataset.references[0] for the exact external source and locator.
   - Also cited at Editorial research route recorded 2026-07-31
   - reference_database; reference source; commit 8138974387d9030542daabe67faaa33eff9356f8; checked 2026-07-31
   - Source use: original_summary
   - Records the current open status and links the literature attached to this exact numbered problem.
   - Source used to formulate or check the problem record.
   - Source used to assess the problem's recorded status.
   - For Erdős's variant on almost-bipartite subgraphs of infinite-chromatic graphs: Records the current open status and links the literature attached to this exact numbered problem.
   - Source named by the research packet.
2. <a id="reference-2"></a>Erdős problem database, data/problems.yaml, commit 8138974387d9030542daabe67faaa33eff9356f8. Problem 74 entry in data/problems.yaml https://github.com/teorth/erdosproblems/blob/8138974387d9030542daabe67faaa33eff9356f8/data/problems.yaml
   - reference_database; reference source; commit 8138974387d9030542daabe67faaa33eff9356f8; checked 2026-07-31
   - Source use: original_summary
   - Pins the maintained database snapshot used for this release's dated status decision.
   - Source used to assess the problem's recorded status.
   - For Erdős's variant on almost-bipartite subgraphs of infinite-chromatic graphs: Pins the maintained database snapshot used for this release's dated status decision.
3. <a id="reference-3"></a>Google DeepMind, Formal Conjectures, formal statement for Erdős Problem 74. GitHub commit bb1c69dab14ad895ac1ccdb7b0c0e0a67c8eb3e1. FormalConjectures/ErdosProblems/74.lean:L132; theorem erdos_74.variants.sqrt; commit bb1c69dab14ad895ac1ccdb7b0c0e0a67c8eb3e1 https://github.com/google-deepmind/formal-conjectures/blob/bb1c69dab14ad895ac1ccdb7b0c0e0a67c8eb3e1/FormalConjectures/ErdosProblems/74.lean#L132
   - reference_database; primary source; commit bb1c69dab14ad895ac1ccdb7b0c0e0a67c8eb3e1; checked 2026-07-31
   - Source use: original_summary
   - Supplies the pinned formal declaration whose human-readable editorial statement is published here.
   - Source used to assess the problem's recorded status.
   - For Erdős's variant on almost-bipartite subgraphs of infinite-chromatic graphs: Supplies the pinned formal declaration whose human-readable editorial statement is published here.