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 >= 1 (due to 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. But I have no idea how to state this formally. Any help?