Here we give some basic definitions from graph theory. A graph is a pair G = (V,E), where V is a finite set (whose elements are called the vertices of G) and E is some collection of two-element subsets of V (called the edges of G). If u and v are vertices of G and e u, v] is an edge of G, then we must have uu, and we say that u and are adjacent. In this case, we also say that e is the edge connecting u with v. (Also note that e {v,u} as well, so the order of u and v in the edge does not matter.) For every vertex u of G, the degree of u is the number of vertices adjacent to u. Notice that if G has n vertices, then the degree of each vertex of G must be a natural number at most n-1 Prove that any graph with n 2 2 vertices must have two distinct vertices with the same degree. An equivalent formulation of this problem is: Given a room with n 2 2 people, any pair of which might or might not shake hands, there must be two different people who shake the same number of hands. [Hint: Consider two cases: (i) there exists a vertex of degree n-1 (equivalently, there is someone who shakes everybody else's hand); (ii) there is no such vertex (person). Use the pigeonhole principle.]