5
$\begingroup$

I came across this proof while studying graph theory and although it instinctively makes sense, I have a problem with a part of it.

Proposition: A non-trivial simple graph $G$ must have at least one pair of vertices whose degrees are equal.

Proof: Let $G$ be a graph with $n$ vertices. Because $G$ is a simple graph, then by definition it doesn't contain multi-edges or loops. Therefore, there appears to be $n$ possible degree values for any vertex, namely $0, ..., n-1$. However, there cannot be both a vertex of degree 0 and a vertex of degree $n - 1$, since the presence of a vertex of degree 0 implies that each of the remaining $n - 1$ vertices is adjacent to at most $n-2$ other vertices. Hence, the $n$ vertices of $G$ can realize at most $n − 1$ possible values for their degrees [This is the part where I have troubles]. Thus, the pigeonhole principle implies that at least two of the $n$ vertices have equal degree.

Isn't this proof based on assumption that there exists a vertex with degree $0$. What happens if that is not case? Does the proof still hold? And why can the $n$ vertices of the graph realize at most $n-1$ possible values? I don't understand that step.

$\endgroup$
5
$\begingroup$

No, there is no assumption that the graph has a vertex of degree $0$: there is simply the observation that it is impossible for a graph on $n$ vertices to have both a vertex of degree $0$ and a vertex of degree $n-1$. If $G$ has a vertex $v$ of degree $n-1$, that vertex is adjacent to all of the other $n-1$ vertices of $G$, and therefore all of those vertices have degree at least $1$, because they all have an edge to $v$. Thus, $G$ cannot have both a vertex of degree $n-1$ and a vertex of degree $0$.

This means that if $G$ has a vertex of degree $n-1$, the only other possible degrees of its vertices are $1,2,\ldots,n-2$: degree $0$ is not possible. Thus, it can have at most the $n-1$ different degrees $1,\ldots,n-1$. And if it has a vertex of degree $0$, the only other possible degrees of its vertices are $1,2,\ldots,n-2$: degree $n-1$ is not possible. In this case it can have at most the $n-1$ degrees $0,\ldots,n-2$.

And of course if $G$ has neither a vertex of degree $0$ nor a vertex of degree $n-1$, the only possible degrees of its vertices are $1,\ldots,n-2$, so that it can have at most these $n-2$ degrees.

In every case, then, $G$ can have at most $n-1$ different degrees for its $n$ vertices, and the pigeonhole principle immediately tells us that two of the vertices must have the same degree.

$\endgroup$
2
  • $\begingroup$ Wow, very simple when you put it that way. Thanks for the clarification. $\endgroup$ – Marwan Jan 16 at 9:50
  • $\begingroup$ @Marwan: You’re welcome. $\endgroup$ – Brian M. Scott Jan 16 at 18:14
3
$\begingroup$

There are $n$ vertices and there are $n$ possible degrees: $0,1,\ldots, n-1$. If no two vertices have same degree, then each possible degree must be attained. In particular, there must be one vertice $v$ of degree $0$ and one vertex $w$ of degree $n-1$. If $n>1$, this is a contradiction

$\endgroup$
0
$\begingroup$

Consider two cases:

  1. There is a vertex of degree $0$. Then the other degrees are in $0,1,\ldots, n-2$. So the degrees are $n$ elements of ${0,1,\ldots, n-2}$ which has size $n-1$. Hence two of the degrees coincide.

  2. There is no vertex of degree $0$. Then the other degrees are in $1,\ldots, n-2, n-1$. So the degrees are $n$ elements of ${1,\ldots, n-1}$ which has size $n-1$. Hence two of the degrees coincide.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.