AoPS - Problem

The problem asks to prove that there exists a connected graph in which the degrees of the nodes are

$1,1,2,2, \ldots, 2000,2000.$ Label the nodes by

$a_1, \ldots, a_{1000}, b_1 \ldots, b_{1000}$ and connect

$a_1$ with all the

$b_i$ 's; connect

$a_2$ with all the

$b_i$ 's, except for

$b_{1000}$ ; connect

$a_3$ with all the

$b_i$ 's, except for

$b_{999}$ and

$b_{1000}$ ; and so on. In this way,

$a_i$ and

$b_i$ have degree

$1001-i,$ for all

$1 \le i \le 1000$ and the resulted graph is connected. Note: The statement doesn't mention explicitly that the graph should be connected, but it's reasonable to assume that this kind of problems refer to road networks.