How to prove it's possible to place $8$ non-attacking rooks on a chessboard with $7$ cells cut out? 
From the 8 × 8 chessboard 7 cells were cut out. Prove that you can put 8 rooks to this board so that none of them can capture another rook.

 A: Here's a hint in the 4x4 case, where we cut out 3 cells:

If all the yellow cells are available, then we place the rooks there, and we are done.  Otherwise, at least one yellow cell is cut out.
If all the red cells are available, then we place the rooks there, and we are done.  Otherwise, at least one red cell is cut out.
etc. for the other colors.
How many cells must we have cut out?
A: Since you wanted a graph-theoretic solution, I will provide one. Assume the board is $n$-by-$n$ and at most $n−1$ squares are removed. Let $R$ be the set of rows and $C$ be the set of columns. The edges of the bipartite graph $G$ with bipartite sets $R$ and $C$ are in the form $\{r,c\}$, where $r\in R$ and $c\in C$ such that the square corresponding to the row $r$ and the column $c$ is not removed. Let $X\subseteq R$. Write $N(X)$ for the set of all $c \in C$ such that $c$ is connected to a vertex in $X$.
If $|X|=0$, then $\big|N(X)\big|=0=|X|$. If $X$ is nonempty, then there are at most $\left\lfloor \frac{n−1}{|X|}\right\rfloor$ columns are not in $N(X)$. Therefore, $\big|N(X)\big|\geq n-\left\lfloor \frac{n−1}{|X|}\right\rfloor$. Clearly, this inequality $|X| \leq n−\left\lfloor \frac{n−1}{|X|}\right\rfloor \leq \big|N(X)\big|$ is satisfied if $|X|=1$, $|X|=n−1$, $|X|=n−2$, or $|X|=n$. For $1<|X|<n−2$, we have 
$$|X|^2−(n−1)|X|+(n−1)=\big(|X|−1\big)\big(|X|−(n−2)\big)+1 \leq 0\,,$$ so $$|X| \leq n−1−\frac{n−1}{|X|} \leq n−\left\lfloor \frac{n−1}{|X|}\right\rfloor \leq \big|N(X)\big|\,.$$
By Hall's Marriage Theorem, there exists a matching that covers $R$, which is a perfect matching on $G$. Having a perfect matching on $G$ is precisely the same as that it is possible to put $n$ rooks on the board such that none can attack another. 
