Why do graph degree sequences always have at least one number repeated? [duplicate]

Solution 1:

It is quite easy to construct an infinite tree whose vertices have distinct degrees, so this observation applies only to finite graphs. Also a graph with a single vertex and no edges has no repeated degrees. So we have to assume at least two vertices.

If there are two isolated vertices then there are two vertices with the same degree. So a counterexample would have a connected component of the graph containing at least two vertices.

This component of the graph has $m\ge 2$ vertices. It has no vertices of degree $0$ and the maximum degree is $m-1$. Since there are $m$ vertices, and only $m-1$ possibilities for the degree of each, two vertices must have the same degree.

Solution 2:

For graphs which aren't simple it's false generally. Example: $ V = \{1,2,3\}$, $ E = \{\{1,2\}, \{2,3\}, \{2,3\}\} $ , where $V$ is the set of vertices and $E$ is the multiset of edges. We have $d(1)=1, d(2)=3, d(3)=2$.