Neighbours of white squares on a chess board and Hall's theorem.

Question

Consider an $m \times n$ chess board with $mn$ even, $m,n \geq 2$, and one black and one white square removed. Label the white squares $1,\dots, \ell$ where $l = mn/2 - 1$, and for each $i \in \{1,\dots,\ell\}$, let $A_i$ be the set of (black) neighbours of white square $i$. How can I prove that for any $S \subseteq \{i,\dots, \ell\}$, $$ \left|\bigcup_{i \in S}A_i \right| \geq |S|,$$ i.e., for any set of $k$ white squares, there are at least $k$ black squares neighbouring at least one white square in this set. It seems intuitively obvious, but I'd like to understand how to prove this rigorously (so that I can use Hall's theorem to prove that there exists a domino tiling for such a board).

Answer 1

For integers $m,n\ge2$ with $mn$ even, let $P(m,n)$ denote the statement: on an $m\times n$ chessboard, any $k$ white squares border at least $k+1$ black squares, provided $0\lt k\lt mn/2$.

The statement $P(m,n)$ implies that an $m\times n$ chessboard will still satisfy Hall's condition (for matching white squares to adjacent black squares) after one black and one white square is removed.

Theorem. If $m,n\in\mathbb N$, $m,n\ge2$, and $mn$ is even, then $P(m,n)$ holds.

The theorem follows directly from the fact that the chessboard graph (whose vertices are the squares, two squares being adjacent if they share a side) has a Hamiltonian circuit. Alternatively, it can be proved by induction using the following lemmas. The easy details are left to the reader.

Lemma 1. $P(2,2)$ and $P(2,3)$ hold.

Lemma 2. Suppose $m,n\in\mathbb N$, $m,n\ge2$, $mn$ even. If $P(m,n)$ holds then $P(n,m)$ holds.

Lemma 3. Suppose $m,n_1,n_2\in\mathbb N$; $m,n_1,n_2\ge2$; and $mn_1$ and $mn_2$ are even. If $P(m,n_1)$ and $P(m,n_2)$ hold, then $P(m,n_1+n_2)$ holds.