# Prove that undirected connected graph w/ |V| >= 2, 2 nodes have same degree

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?

• Try assuming the graph has no two vertices with the same degree, and writing the degree sequence of the vertices (the list of degrees in non-decreasing order). Keep in mind that there are $n$ vertices and the maximum degree is $n - 1$. – Manuel Lafond Feb 2 '15 at 18:05

## 1 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?

• Why is the smallest possible degree one? You can have a node with a degree of zero. – Danny Dan Sep 1 '17 at 22:16