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 ( | V ( H 1 ) | , | V ( H 2 ) | ) ) 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 ) ∪ E ( H 2 ) = E ( Q k ) .