How to prove that at least two vertices have the same degree in any graph? I want to prove that at least two vertices have the same degree in any graph (with 2 or more vertices). I do have a few graphs in mind that prove this statement correct, but how would I go about proving it (or disproving it) for ALL graphs?
 A: Say graph is simple with no loops and that all vertices have different degree $d_1,d_2,...d_n$, then $$\{d_1,d_2,...d_n\} = \{0,1,2...,n-1\}$$
So there is a vertex with degree $n-1$ and a vertex with degree $0$. A contradiction.
A: I assume we're talking about finite graphs.  I'm pretty sure your statement is false for infinite graphs.
Assume that a finite graph $G$ has $n$ vertices.  Then each vertex has a degree between $n-1$ and $0$.  But if any vertex has degree $0$, then no vertex can have degree $n-1$, so it's not possible for the degrees of the graph's vertices to include both $0$ and $n-1$.  Thus, the $n$ vertices of the graph can only have $n-1$ different degrees, so by the pigeonhole principle at least two vertices must have the same degree. 
A: EDIT: Graphs are typically defined as being finite. Infinite graphs are a generalization. I did not know this at the time of the post. I will leave this answer up though in case anyone finds it useful.
Here is a counterexample.
Let $G$ be a graph on the positive integers where there is an edge from $x$ to $y$ if $x < y \le 2x$. Note that we will ignore the direction of the edges. So $2$, for example, is neighbored by $1$, $3$, and $4$.
Let $j$ and $k$ be distinct positive integers. Without loss of generality assume that $j < k$. Note that $deg(j) = j + \lfloor j/2 \rfloor$ and $deg(k) = k + \lfloor k/2 \rfloor$. We have that
$$j < k$$
$$\lfloor j/2 \rfloor \le \lfloor k/2 \rfloor$$
$$j + \lfloor j/2 \rfloor < k + \lfloor k/2 \rfloor$$
$$deg(j) < deg(k)$$
$$deg(j) \neq deg(k)$$
Therefore, no two different vertices will have the same degree. $\square$
