So I know this is true, but I have no idea how to formally state that this is true:
Prove that an undirected, connected graph with two or more nodes(vertices) contains two nodes that have equal degree.
So I know that 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 $\geq 1$ (due to definition of connected) and $\leq 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. But I have no idea how to state this formally. Any help?
Best Answer
HINT: 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 $n-1$, so the set of possible degrees is $D=\{1,2,\ldots,n-1\}$. How many different numbers are in $D$? How many nodes does $G$ have?