Erdős Problem #111

Erdős Problem 111: distance from bipartiteness

Statement and scope

For a graph $G$ of chromatic number $\aleph_1$, let $h_G(n)$ be the maximum, over its $n$-vertex subgraphs, of the minimum number of edges whose removal makes that subgraph bipartite. The question asks whether $h_G(n)/n\to\infty$. We prove a uniform positive linear lower bound depending on $G$, but superlinear growth is unresolved here.

This revises the earlier GPT-5.2 max-cut and odd-cycle observations and adds the uncountable disjoint-cycle argument. Source: https://www.erdosproblems.com/111. These are elementary partial results, not a claimed new resolution.

Two useful finite identities

For a finite graph $H$ write $\tau(H)$ for its edge-deletion distance from bipartiteness. Then \[ \tau(H)=e(H)-\operatorname{MaxCut}(H). \tag{1} \] Indeed, retaining all edges across any vertex bipartition gives a bipartite graph. Conversely every bipartite spanning subgraph retains only edges of some cut. Also, if $H$ contains $t$ edge-disjoint odd cycles, then $\tau(H)\ge t$, because at least one edge from each cycle must be removed.

For every $n$-vertex graph, \[ \tau(H)\le {n\choose2}-\left\lfloor\frac{n^2}{4}\right\rfloor =\left\lfloor\frac{(n-1)^2}{4}\right\rfloor. \tag{2} \] Choose any partition into $\lfloor n/2\rfloor$ and $\lceil n/2\rceil$ vertices and discard its internal edges; there are at most the number on the right.

Uncountable chromatic number forces many disjoint odd cycles

Choose a maximal family $\mathcal C$ of pairwise vertex-disjoint finite odd cycles. Such a family exists by the usual maximality principle. It cannot be countable. If it were, the union $S$ of its vertices would be countable, and $G-S$ would have no odd cycle by maximality. A graph with no finite odd cycle is bipartite: in each connected component, parity of path length from a chosen root is well-defined, since two paths of opposite parity would give an odd closed walk and hence an odd cycle.

Colour $G-S$ with two colours and give the vertices of $S$ distinct further colours. This countable colouring contradicts $\chi(G)=\aleph_1$.

There are only countably many odd cycle lengths. Thus some odd integer $\ell\ge3$ occurs for uncountably many members of $\mathcal C$; otherwise $\mathcal C$ would be a countable union of countable sets. For every $n$, take $\lfloor n/\ell\rfloor$ of these cycles and add arbitrary vertices to reach $n$ vertices. Their cycles are still edge-disjoint, so \[ h_G(n)\ge\left\lfloor\frac n\ell\right\rfloor,\qquad \liminf_{n\to\infty}\frac{h_G(n)}n\ge\frac1\ell>0. \tag{3} \] Additional edges between the chosen vertices cannot invalidate this lower bound.

Remaining gap

The fixed-length packing argument gives only a fixed linear coefficient. A disjoint union of $\ell$-cycles has linear deletion distance and chromatic number three, illustrating the limitation of the packing method; it is not a counterexample under the uncountable-chromatic hypothesis. To answer the question one must force arbitrarily large deletion cost per vertex, rather than just arbitrarily many disjoint cycles.

COMPLETION ESTIMATE

COMPLETION: 30%

Erdős Problem #111

1) FORMAL RESTATEMENT

Let $G$ be a (possibly infinite) simple undirected graph. For each $n\in\mathbb N$, define $h_G(n)$ to be the least integer $t$ such that every induced subgraph $H$ of $G$ with $|V(H)|=n$ can be made bipartite by deleting at most $t$ edges. Equivalently, \[ h_G(n):=\max\{\tau(H):\;H\subseteq G,\ |V(H)|=n\}, \] where $\tau(H)$ is the minimum number of edges that must be deleted from $H$ to make it bipartite.

Question: determine/estimate the growth of $h_G(n)$ as $n\to\infty$. In particular, is it true that \[ \frac{h_G(n)}{n}\to\infty\quad\text{for every graph $G$ with }\chi(G)=\aleph_1\ ? \]

2) QUICK LITERATURE/CONTEXT CHECK

From the problem text:

• Any $G$ with $\chi(G)=\aleph_1$ must satisfy $h_G(n)\gg n$ since it contains $\aleph_1$ vertex-disjoint odd cycles of some fixed length.
• There exists such a $G$ with $h_G(n)\ll n^{3/2}$.
• Erdős conjectured improvement to $\ll n^{1+\varepsilon}$ for all $\varepsilon>0$.

No further sources are used here.

3) ATTACK PLAN

To get quantitative bounds one needs to understand $\tau(H)$ for finite graphs $H$ and then produce (or obstruct) subgraphs $H\subseteq G$ that force large $\tau(H)$. I provide two problem-specific lemmas: an exact reformulation of $\tau(H)$ in terms of maximum cuts, and a lower bound in terms of edge-disjoint odd cycles.

4) WORK

Lemma 111.1 (bipartite edge-deletion equals "edges minus max-cut").

For any finite graph $H=(V,E)$, \[ \tau(H)=|E(H)|-\operatorname{MaxCut}(H), \] where $\operatorname{MaxCut}(H)$ is the maximum number of edges crossing a bipartition $V=A\sqcup B$.

Proof. If we partition $V=A\sqcup B$, then the edges crossing the cut form a bipartite subgraph (all edges go between $A$ and $B$). Keeping only those edges deletes exactly $|E|-|E(A,B)|$ edges and makes the graph bipartite. Minimizing deletions is therefore equivalent to maximizing $|E(A,B)|$, i.e. \[ \tau(H)=\min_{A\sqcup B} (|E|-|E(A,B)|)=|E|-\max_{A\sqcup B}|E(A,B)|. \] This is precisely $|E(H)|-\operatorname{MaxCut}(H)$. $\square$

Lemma 111.2 (edge-disjoint odd cycles force deletions).

Let $H$ be a finite graph containing $t$ edge-disjoint odd cycles. Then $\tau(H)\ge t$.

Proof. Every bipartite graph contains no odd cycle. To make $H$ bipartite, we must destroy each of the $t$ odd cycles by deleting at least one edge from each cycle. If the cycles are edge-disjoint, the edges needed to break different cycles are distinct, so at least $t$ edges must be deleted in total. Hence $\tau(H)\ge t$. $\square$

Corollary 111.3 (linear lower bound from vertex-disjoint odd cycles).

If $H$ contains $t$ vertex-disjoint odd cycles, then $\tau(H)\ge t$. In particular, if $H$ is a disjoint union of $t$ odd cycles, then $\tau(H)=t$.

Proof. Vertex-disjoint cycles are edge-disjoint, so Lemma 111.2 applies. For the "in particular": deleting one edge per cycle makes each component a path and hence bipartite, so $\tau(H)\le t$; combined with $\tau(H)\ge t$ gives equality. $\square$

5) VERIFICATION (FAST REALITY CHECK)

• For $H=C_{2r+1}$ (single odd cycle), Lemma 111.2 gives $\tau(H)\ge1$, and indeed deleting one edge breaks the cycle, so $\tau(H)=1$.
• Lemma 111.1: check on $H=K_3$. Here $|E|=3$ and $\operatorname{MaxCut}(K_3)=2$, so $\tau=1$, consistent.
• For disjoint union of $t$ triangles, $|E|=3t$, maxcut is $2t$, so $\tau=t$.

6) FINAL

UNRESOLVED.

(i) Strongest fully proved partial result obtained here. Exact identity $\tau(H)=|E|-\operatorname{MaxCut}(H)$ for finite $H$ (Lemma 111.1), and the lower bound $\tau(H)\ge t$ from $t$ edge-disjoint odd cycles (Lemma 111.2).

(ii) Exact first gap. For graphs $G$ with $\chi(G)=\aleph_1$, determine whether one must have $h_G(n)/n\to\infty$; current lemmas only show $h_G(n)\gg n$ in the presence of linearly many disjoint odd cycles.

(iii) Top 3 next moves (concrete targets).

1. Prove that $\chi(G)=\aleph_1$ forces, for arbitrarily large $n$, an $n$-vertex subgraph $H$ with many edge-disjoint odd cycles (to feed Lemma 111.2).
2. Conversely, attempt to build $\aleph_1$-chromatic graphs where every $n$-vertex subgraph has maxcut very close to $|E|$, i.e. is "almost bipartite".
3. Translate the problem to extremal questions about maxcut in $n$-vertex subgraphs of $G$.

(iv) Minimal counterexample structure. A negative answer would be a graph $G$ with $\chi(G)=\aleph_1$ and a constant $C$ such that every $n$-vertex subgraph $H$ satisfies $\tau(H)\le Cn$ for all large $n$.