# The vertices of the $n$-cube are painted in two colors

The vertices of the $n$-dimensional cube are painted in two colors. The number of vertices of each color is the same ($2^{n-1}$). Prove that at least $2^{n-1}$ edges connect vertices of different colors.

• Do you mean coloring in the graph-theoretical sense, i.e., coloring of the hypercube $Q_n$? – user12344567 Jun 26 '15 at 10:42
• @ blazs: No, I mean arbitrary painting of hypercube. – grizzly Jun 26 '15 at 10:46
• Ok, just to make perfectly sure: you allow vertices connected by an edge to have the same color? – user12344567 Jun 26 '15 at 10:47
• Yes, of course. – grizzly Jun 26 '15 at 10:48
• @grizzly Where did this problem come from? What have you tried? – Tad Jun 27 '15 at 0:02

The question can be phrased as follows: for any subset $S$ of $2^{n-1}$ vertices in the $n$-dimensional hypercube graph $H_n$, show that $|\delta(S)|\ge2^{n-1}$, where $$\delta(S) := \{(u,v)\mid u\in S, v\notin S\}$$ is the boundary of $S$.
It is a standard result of spectral graph theory that, for any subset $S$ of a graph $G$, $$|\delta(S)| \ge \lambda_2 |S| (1-|S|/|V(G)|)$$ where $0=\lambda_1\le\lambda_2\le\cdots\le\lambda_{n-1}$ are the eigenvalues of the Laplacian of $G$.
Now, $H_n$ is the $n$-fold (Cartesian) graph product of the graph $H_1$ having two vertices and one edge. The eigenvalues of (the Laplacian of) $H_1$ are $0$ and $2$, and it follows that the eigenvalues of $H_n$ are $0, 2,\ldots, 2n$, each with multiplicity $\binom nk$. Thus, for $H_n$, we have $\lambda_2=2$; it follows that if $|S|=2^{n-1}$, we have $$|\delta(S)| \ge \lambda_2 |S| (1-|S|/|V(H_n)|)=2\cdot 2^{n-1}\cdot(1-2^{n-1}/2^n)=2^{n-1},$$ as required.