Problem: Some checkers placed on an $n \times n$ checkerboard satisfy the following conditions:
\begin{enumerate}
  \ii[(a)] every square that does not contain a checker shares a side with one that does;
  \ii[(b)] given any pair of squares that contain checkers,
  there is a sequence of squares containing checkers,
  starting and ending with the given squares,
  such that every two consecutive squares of the sequence share a side.
\end{enumerate}
Prove that at least $(n^{2}-2)/3$ checkers have been placed on the board.

Solution: Take a spanning tree on the set $V$ of checkers
where the $|V|-1$ edges of the tree are given by orthogonal adjacency.
By condition (a) we have
\[ \sum_{v \in V} (4-\deg v) \ge n^2 - |V| \]
and since $\sum_{v \in V} \deg v = 2(|V|-1)$ we get
\[ 4|V| - \left( 2|V|-2 \right) \ge n^2 - |V| \]
which implies $|V| \ge \frac{n^2-2}{3}$.