In a group of n friends (n >= 2), atleast 2 of them will have same no: of
Reformulating as a graph theory problem
In an undirected graph G (with no self-loops) with n = |V| >= 2, atleast 2
vertices will have same degree.
Proof. We use proof by cases
(case 1). G is connected
The degree of a vertex can be any of n-1 different values 1, 2,...,n-1(A
vertex with degree 0 will imply that G is not connected). There are n
vertices in the graph. So atleast 2 of them should have same degree by
(case 2). G is not connected
The degree of a vertex can be any of n-1 different values 0,1,...,n-2 (A
vertex with degree n-1 will imply that G is connected). A similar argument
as case 1 applies.