## Whole Rectangles

A short introduction to Graph Theory is needed for this one. If you already are familiar with Graph Theoretic constructs feel free to skip it.

### Short Intro to Graph Theory

A *graph**G*, is a pair *(V,E)* where *V* is a set of ** vertices** and

*E*is a set of

**. Each**

*edges***is an unordered pair of the form**

*edge**(u, v)*where

*u*and

*v*are

**(i.e. they belong to**

*vertices**V*). The

**of a vertex**

*degree**t*(denoted

*deg(t)*) is the number of edges containing it:

In this post I only consider *finite* and *simple* graphs. A ** finite graph** is a graph whose vertex-set

*V*is finite. A

**is a graph in which there are no loops (i.e. edges of the form**

*simple graph**(u, u)*) and no multiple edges (i.e.

*E*is a proper set so it cannot contain the same element twice).

The following is a trivial claim:

*The sum of the degrees in a graph equals twice the number of edges.*

It is trivial to prove this claim by induction on the number of edges (on a graph with no edges it is clear, and by adding an edge to the edge set of the graph the sum of degrees increases by two \(\blacksquare\)).

### The Riddle

A rectangle is called ** whole** if at least one of its sides is an integer. For example, a rectangle of 2 by \(\frac{3}{5}\) is whole as well as a rectangle of \(\sqrt{5}\) by 3. A rectangle of \(\frac{1}{2}\) by \(\frac{1}{2}\) is not whole. Examples:

A set *T* of rectangles constitues a ** tiling** of a rectangle

*R*if the rectangles in

*T*are disjoint and for every point

*p*in

*R*there is a rectangle

*S*in

*T*such that

*p*belongs to

*S*. Example:

**Prove that if R is a rectangle and T is a tiling of R consisting only of whole rectangles (i.e. every rectangle S in T is whole) then R is whole.**