Use the pigeonhole principle to prove the following Every co

Use the pigeonhole principle to prove the following: Every connected undirected simple graph with at least 2 nodes has two nodes with the same degree

Solution

Use the pigeonhole principle. If G has n nodes, you’ve already observed that the smallest and largest possible degrees of a node of G are 1 and n1, so the set of possible degrees is D={1,2,…,n1}.there are n-2 degrees but n nodes hence at least 2 vertices should have same degree .

{ connected means that each node has at least 1 degree and undirected means that if a node has 1 degree, the node it connects to has at least 1 degree. So in my mind, I know that if there are 2 nodes, they each have 1 degree. If there are 4 nodes there the max degree is 3, which is one node connecting to all other nodes. Thus, the remaining 3 nodes have to have a degree >= 1 (due to the definition of connected) and <= 3, since there are only 3 other nodes it can connect to. So no matter what degree the remaining nodes have it will either be 3,3,3; 3,2,1; 2,2,1; etc there will always be 2 nodes with the same degree. and so on for more nodes}