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.
 A: 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.
One reference which seems to have all of this, with some more detail, is Alexandra Kolla's lecture notes.
