Here we give some basic definitions from graph theory. A graph is a pair G = (V,
ID: 3590399 • Letter: H
Question
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.]Explanation / Answer
Let G be the graph with number of vertices (n) >= 2. Then, there can be two inferences:
a. The maximal degree of any vertex will either be less to equal to n-1.
b. If G is not connected, the maximal degree will be strictly less than n-1.
Case 1: G is connected
Set of vertex of degrees will be a subset of {1,2,..,n-1}. Since, G has n vertices, we can use pigeon hole principle to find two vertices of the same degree in G.
Case 2: G is not connected
Set of vertex of degrees will be a subset of {0, 1, 2, · · · , n 2}. Hence, we can find two vertices of the same degree in G by using pigeon-hole principle.