Induced subgraphs of hypercubes

Let Q(k) denote the k-dimensional hypercube on 2(k) vertices. A vertex in a subgraph of Q(k) is full if its degree is k. We apply the Kruskal-Katona Theorem to compute the maximum number of full vertices an induced subgraph on n <= 2(k) vertices of Q(k) can have, as a function of k and n. This is then used to determine min(max(vertical bar V(H-1)vertical bar. vertical bar V(H-2)vertical bar)) where (i) H-1 and H-2 are induced subgraphs of Q(k), and (ii) together they cover all the edges of Q(k), that is E(H-1) boolean OR E(H-2) = E(Q(k)). (c) 2012 Elsevier Ltd. All rights reserved.