Skip to content

Erdős problem 74

Let f(n)→∞f(n)\to \infty possibly very slowly. Is there a graph of infinite chromatic number such that every finite subgraph on nn vertices can be made bipartite by deleting at most f(n)f(n) edges?

Sources

The source's own material, retained exactly.

4 retained statements36c6d0fef71a

Open selected source

FormalConjectures/ErdosProblems/

74.lean

Retained formal statement4 of 4

The set of minimum edge distances to bipartite for subgraphs of size n is bounded above. A graph on n vertices has at most n choose 2 edges, and deleting all of them makes the graph bipartite, providing a straightforward upper bound.

FormalConjectures/ErdosProblems/74.leanErdos74.SimpleGraph.subgraphEdgeDistsToBipartite_bddAbove1 lineExact file
∀ {V : Type u} (G : SimpleGraph V) (n : ℕ), BddAbove (Erdos74.SimpleGraph.subgraphEdgeDistsToBipartite G n)
TestStatement only, no proof