17

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

$(1, 2, 2, 3)$ = Valid, as you can see, because the $2$ is repeated.
$(1, 2, 3)$ = Not possible to construct a graph with because all numbers are unique.

I know that the graph degree sum must be even, but in this case, both are even.

Our professor said it had to do with Combinatorics, but we never touched that topic.

EDIT: Loops are not allowed.

Roberto1
  • 227
  • 1
    It depends on exactly what your definition of a "graph" is, but if each edge connects two distinct vertices, in your example $(1,2,3),$ each vertex can connect to at most two others, so it is not possible for the last vertex to have degree $3$. Mark Bennet explains how this works in general. – David K Jun 15 '15 at 09:17
  • I should have added that graphs with loops are not allowed here. – Roberto1 Jun 15 '15 at 09:19
  • 1
    Yes, "no loops" would be implied by "two distinct edges," but you are right: that condition is required. – David K Jun 15 '15 at 09:22
  • 3
    Look up "Pigeonhole Principle", it's very useful to prove things like this. – CaptainCodeman Jun 15 '15 at 10:44

2 Answers2

30

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.

Mark Bennet
  • 100,194
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$.

ninjaaa
  • 440