Show that it is impossible, using 1x2 rectangles, to exactly cover an 8x8 square from which 2 opposite 1x1 corner squares have been removed.
When I do this on paper, it is clear that it is not possible, but I do not know how to write this down in graph theory language. Some help would be much appreciated. Thanks
On
Ross's answer is probably the simplest, most elegant proof. Here's a similar idea that phrases it more in terms of graph theory:
Create a graph with each vertex corresponding to one of the squares of the 8x8 grid with opposite corner squares removed, so that two vertices are adjacent in the graph if and only if the corresponding squares are adjacent in the grid. Now covering the grid with 1x2 rectangles is equivalent to finding a perfect matching in the graph. But the graph is bipartite with one partite $A$ set of size 30, and the other partite set $B$ of size 32, which cannot have a perfect matching since $|A| \neq |B|$.
Color the board like a chessboard. Count the squares of each color-there will be $30$ of one color and $32$ of each color. Each $1 \times 2$ rectangle covers squares of opposite colors, so the set of rectangles cover the same number of each color.