How many vertices with same degree

Question

In a simple graph with $2000$ vertices without any vertex with $\deg(a)=0$, we have exactly two vertices which have the same degree. What is the degree of these two?

I think I should use pigeon hole principle because we have two elements with the same property. But I don,t know how. Can someone guide me to solve this please?

My attempt:

The graph vertices can have degrees $0$ to $n-1$. But we can't have both $0$ degree and $n-1$ degree in the same graph. So for any vertex $a$, $\deg(a)$ is either in $\{1,2,\dots,1999\}$ or $\{0,1,\dots,1998\}$. We don’t have any vertex with degree $0$. So for any vertex $a$,degree $a$ is in $\{1,2,\dots,1999\}$. Handshake theorem states that sum of all the degrees of vertices is $2m$. So we can say $1+2+\dots+1999+x=2m$ where $x$ is the degree shared by two different vertices (By pigeon hole principle, such $x$ exists). But we don’t know $m$. So... Now what?

Answer 1

Some intuition:

1. In this graph, there must be a vertex of degree 1999. This vertex connects with every other vertex. There can be no other vertex with degree 1999, because otherwise there would be no vertex of degree 1.
2. In this graph, there must be a vertex of degree 1998. This vertex connects to all other vertices (including the one of degree 1999) except for the vertex of degree 1. There can be no other vertex with degree 1998, because otherwise, there would be no vertex of degree 2.
3. ...

Answer 2

Say a graph has $2n$ vertices all but exactly two have different degree. Suppose there is no discrete vertex in $G$. Then the degree of the vertices with same the degree is $n$.

Proof (with induction): For $n=1$ is obviously true. Say we have degrees $d_1\leq d_2\leq...\leq d_{2n+2}$. Then $$\{d_1,d_2,...,d_{2n+2}\} =\{1,2,...,2n+1\}$$ Clearly $d_1=1$ and $d_{2n+2}=2n+1$. So if we delete vertices $v_1$ and $v_{2n+2}$ we get the same tipe of graph $G'=G\setminus \{v_1,v_{2n+2}\} =: \{v'_1,v'_2,...v'_{2n}\}$ with $2n$ vertices and degrees: $$d_1'=d_2-1\leq d_2'=d_3-1\leq ...\leq d_{2n}'=d_{2n+1}-1$$
By induction hypothetis $v'_n$ and $v'_{n+1}$ have a degree $n$ and there for there are two vertices with degree $n+1$ in $G$.