Another proof of Albert's lemma (and one that I believe is much more elegant than the others presented):
I will prove a stronger lemma instead. Namely:
(A proof of the reduced statement follows. This proof is similar to Gareth's answer to the same question, but does not rely on an arbitrary choice of "leftmost".)
Here's (what I think is) a simpler proof of Albert's lemma than the one in loopy_wall's answer. We'll find either a king-path of 0-squares connecting N and S sides, or a king-path of 1-squares connecting W and E sides. The basic idea is to walk along the boundary between 0-squares and 1-squares until we reach an edge of the board. So here's an example board; ...
Every pair of zeros and every pair of ones are connected via some King chain
is confusing. If you mean that every $1$ can be reached from every other $1$ by the traversal rules (similarly for $0$), then I think 8 is a minimum. If we can have disconnected pairs,
gets you to 7.
As for a proof, there might be fertile ground in looking at what can stop a path (...