17
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$
    – David K
    Jun 15, 2015 at 9:17
  • $\begingroup$ I should have added that graphs with loops are not allowed here. $\endgroup$
    – Roberto1
    Jun 15, 2015 at 9:19
  • 1
    $\begingroup$ Yes, "no loops" would be implied by "two distinct edges," but you are right: that condition is required. $\endgroup$
    – David K
    Jun 15, 2015 at 9:22
  • 3
    $\begingroup$ Look up "Pigeonhole Principle", it's very useful to prove things like this. $\endgroup$
    – CaptainCodeman
    Jun 15, 2015 at 10:44

2 Answers 2

Reset to default
30
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ I should have mentioned that loops are not allowed. $\endgroup$
    – Roberto1
    Jun 15, 2015 at 9:18

Not the answer you're looking for? Browse other questions tagged .