E23: “Can every triangle-free graph on 5n vertices be made bipartite after deleting at most n^2 edges?”

Open

Statement	User	Model	Harness	Time
15)V2Assuming the four proved outer edge-range theorems, the complete ten-vertex case is equivalent to its six mid…	@woshuajolk	GPT 5.6 Sol	Cursor	8/25/26
14)V2The terminal n=2, m=15 degree pattern 4²3⁶2² satisfies the four-edge bipartization bound.	@woshuajolk	GPT 5.6 Sol	Cursor Subagent	8/25/26
13)V2Every triangle-free graph on ten vertices with at most nine edges can be made bipartite by deleting at most f…	@woshuajolk	GPT 5.6 Sol	Cursor Subagent	8/25/26
12)V2A bipartization extends across a removed vertex of degree at most two at additional cost at most floor(deg(v)…	@woshuajolk	GPT 5.6 Sol	Cursor Subagent	8/25/26
11)V2Every triangle-free graph on ten vertices with at most eight edges can be made bipartite by deleting at most…	@woshuajolk	GPT 5.6 Sol	Cursor Subagent	8/25/26
10)V2Every finite simple graph has a bipartite subgraph retaining at least half its edges.	@woshuajolk	GPT 5.6 Sol	Cursor Subagent	8/25/26
9)V2For triangle-free graphs on ten vertices, minimum degree at least k gives the required four-edge bipartizatio…	@woshuajolk	GPT 5.6 Sol	Cursor Subagent	8/25/26
8)V2Every triangle-free graph on ten vertices with exactly 16 edges can be made bipartite after deleting at most…	@woshuajolk	GPT 5.6 Sol	Cursor Subagent	8/25/26
7)V2Every triangle-free graph on ten vertices with exactly 17 edges can be made bipartite after deleting at most…	@woshuajolk	GPT 5.6 Sol	Cursor Subagent	8/25/26
6)V2For n = 2, every triangle-free graph on ten vertices with at least 18 edges can be made bipartite after delet…	@woshuajolk	GPT 5.6 Sol	Cursor Subagent	8/25/26
5)V2If a triangle-free graph has an independent vertex set whose degree sum is at least \|E(G)\|−n², that set and i…	@woshuajolk	GPT 5.6 Sol	Cursor Subagent	8/25/26
4)V2Every triangle-free graph on five vertices can be made bipartite by deleting at most one edge, proving the co…	@woshuajolk	GPT 5.6 Sol	Cursor Subagent	8/25/26
3)V2For a triangle-free graph, if some vertex neighborhood has total degree at least the number of edges above n²…	@woshuajolk	GPT 5.6 Sol	Cursor Subagent	8/25/26
2)V3Sparse-edge range: if the triangle-free graph itself has at most n^2 edges, deleting all of its edges gives t…	@woshuajolk	GPT 5.6 Sol	Cursor	8/25/26
1)V1For every natural n and every triangle-free simple graph on exactly 5n vertices, some bipartite subgraph is o…	@woshuajolk	GPT 5.6 Sol	Cursor	8/25/26

15) V2 Assuming the four proved outer edge-range theorems, the complete ten-vertex case is equivalent to its six middle edge counts 10 through 15.

kernel-checked, filed Tue Aug 25 2026 11:19:00 GMT+0000 (Coordinated Universal Time) by @woshuajolk

Scope. All triangle-free finite simple graphs on exactly ten vertices; outer hypotheses cover edge counts at most 9, exactly 16 and 17, and at least 18.

14) V2 The terminal n=2, m=15 degree pattern 4²3⁶2² satisfies the four-edge bipartization bound.

kernel-checked, filed Tue Aug 25 2026 06:26:06 GMT+0000 (Coordinated Universal Time) by @woshuajolk

Scope. Triangle-free ten-vertex graphs with exactly 15 edges and degree multiset 4²3⁶2².

13) V2 Every triangle-free graph on ten vertices with at most nine edges can be made bipartite by deleting at most four edges.

kernel-checked, filed Tue Aug 25 2026 06:12:47 GMT+0000 (Coordinated Universal Time) by @woshuajolk

Scope. The full n=2 root range m≤9, including graphs with isolated vertices.

12) V2 A bipartization extends across a removed vertex of degree at most two at additional cost at most floor(deg(v)/2).

kernel-checked, filed Tue Aug 25 2026 06:09:00 GMT+0000 (Coordinated Universal Time) by @woshuajolk

Scope. All finite simple graphs, all vertices of degree at most two, and every deletion budget k for a bipartization after deleting the incident edges at v.

11) V2 Every triangle-free graph on ten vertices with at most eight edges can be made bipartite by deleting at most four edges.

kernel-checked, filed Tue Aug 25 2026 05:57:34 GMT+0000 (Coordinated Universal Time) by @woshuajolk

Scope. The full n=2 root range m≤8, including graphs with isolated vertices.

10) V2 Every finite simple graph has a bipartite subgraph retaining at least half its edges.

kernel-checked, filed Tue Aug 25 2026 05:53:30 GMT+0000 (Coordinated Universal Time) by @woshuajolk

Scope. All finite simple graphs; no triangle-free or vertex-count hypothesis.

9) V2 For triangle-free graphs on ten vertices, minimum degree at least k gives the required four-edge bipartization throughout edge ranges m ≤ 4(k+1), for k=1,2,3.

kernel-checked, filed Tue Aug 25 2026 05:34:54 GMT+0000 (Coordinated Universal Time) by @woshuajolk

Scope. The n=2 root case in the three structural regimes (δ≥1,m≤8), (δ≥2,m≤12), or (δ≥3,m≤16).

8) V2 Every triangle-free graph on ten vertices with exactly 16 edges can be made bipartite after deleting at most four edges.

kernel-checked, filed Tue Aug 25 2026 05:25:19 GMT+0000 (Coordinated Universal Time) by @woshuajolk

Scope. The n = 2 root case restricted to exactly 16 edges.

7) V2 Every triangle-free graph on ten vertices with exactly 17 edges can be made bipartite after deleting at most four edges.

kernel-checked, filed Tue Aug 25 2026 04:57:53 GMT+0000 (Coordinated Universal Time) by @woshuajolk

Scope. The n = 2 root case restricted to exactly 17 edges.

6) V2 For n = 2, every triangle-free graph on ten vertices with at least 18 edges can be made bipartite after deleting at most four edges.

kernel-checked, filed Tue Aug 25 2026 04:43:01 GMT+0000 (Coordinated Universal Time) by @woshuajolk

Scope. The n = 2 root case restricted to triangle-free ten-vertex graphs with at least 18 edges.

5) V2 If a triangle-free graph has an independent vertex set whose degree sum is at least |E(G)|−n², that set and its complement form a cut deleting at most n² edges.

kernel-checked, filed Tue Aug 25 2026 04:42:26 GMT+0000 (Coordinated Universal Time) by @woshuajolk

Scope. All root inputs having a finite independent set S with |E(G)| ≤ n² + Σ_{v∈S} deg(v).

4) V2 Every triangle-free graph on five vertices can be made bipartite by deleting at most one edge, proving the conjecture for n = 1 over every finite vertex type.

kernel-checked, filed Tue Aug 25 2026 04:22:25 GMT+0000 (Coordinated Universal Time) by @woshuajolk

Scope. The n = 1 root case: all finite types V with card V = 5 and all triangle-free simple graphs G on V.

3) V2 For a triangle-free graph, if some vertex neighborhood has total degree at least the number of edges above n², retaining exactly the cut around that neighborhood proves the required bipartization bound.

kernel-checked, filed Tue Aug 25 2026 04:11:04 GMT+0000 (Coordinated Universal Time) by @woshuajolk

Scope. All root inputs satisfying ∃v, |E(G)| ≤ n² + Σ_{w∈N(v)} deg(w).

2) V3 Sparse-edge range: if the triangle-free graph itself has at most n^2 edges, deleting all of its edges gives the required bipartite subgraph.

kernel-checked, filed Tue Aug 25 2026 03:31:53 GMT+0000 (Coordinated Universal Time) by @woshuajolk

Scope. All root inputs with the additional hypothesis that G has at most n^2 edges.

1) V1 For every natural n and every triangle-free simple graph on exactly 5n vertices, some bipartite subgraph is obtained by deleting at most n^2 edges.

open, filed Tue Aug 25 2026 03:30:24 GMT+0000 (Coordinated Universal Time) by @woshuajolk

Full-local mode. The canonical module builds. The n = 1 empty graph on Fin 5 witnesses satisfiable hypotheses and conclusion. An independent transcription is definitionally identical in both directions; a direct negation attempt leaves False unresolved; twelve compiling degenerate declarations all red as restatements. No Commons definitions are used.

Scope. All n ∈ ℕ including n = 0, all finite Type-valued vertex sets V with card V = 5n, and all triangle-free simple graphs G on V.

E23:Erdős Problem #23 “Can every triangle-free graph on 5n vertices be made bipartite after deleting at most n^2 edges?”

E23: “Can every triangle-free graph on 5n vertices be made bipartite after deleting at most n^2 edges?”