A large rectangle is subdivided into smaller rectangles, each of which has at least one pair of sides of integer length. Prove that the large rectangle also has at least one pair of sides of integer length.
Solution
Label the large rectangle by and place it in the plane so that its lower-left corner is at with sides parallel to .
Let be the set of vertices of the small rectangles whose both coordinates are integers, and let be the set of all the small rectangles. We form a bipartite graph on the vertex set by joining each point in to every rectangle in of which it is a vertex. Observe that each small rectangle has either 0, 2, or 4 vertices in (because of integer length side), so it contributes an even number of edges. Hence the total number of edges in this bipartite graph is even. On the other hand, each point in that is not a corner of is a vertex of exactly 2 or 4 small rectangles, and so also has even degree.
Since is in and is a corner of exactly one small rectangle, it has odd degree. Therefore there must be another vertex in of odd degree. The only vertices of odd degree can be corners of , so at least one other corner of lies in . In particular, either the width or the height of is an integer.