Pigeonhole Principle, Discrete Mathematics, Combinatorics, Mathematical Logic, Problem Solving.
there must exist at least 2 vertices with the same degree. Proof Consider a connected graph with n vertices. The degree of any vertex has a range of 0,1,…,n−1. Also, there can never be a vertex with n−1n-1n−1 degrees and another vertex of 0 degrees because these two need to be adjacent to meet the