Consider a graph where towns are vertices and highways are edges. The problem can be interpreted as: “construct a tree that includes all the specified edges and each vertex has a specified degree.”

If \(\sum D_i\neq 2N-2\), then it is obviously impossible. Consider when \(\sum D_i= 2N-2\).

First, let’s consider if the condition can be satisfied.

Since the final graph becomes a tree, no new edge will be added between a pair of vertices belonging in the same connected component. Therefore, the lack of degrees can be considered for each connected component. For each component, if the sum of shortages of degrees of vertices in the component is \(n\), we denote that “it wants \(n\) degrees”.

In fact, if the condition can be satisfied, then the following algorithm constructs the tree.

• First, repeat the following operation as many times as possible: add an edge between a connected component \(X\) that wants \(1\) degree, and a connected component \(Y\) that wants \(2\) or more degrees.
• When the operation above is impossible, if there are exactly two remaining connected components, each of which wanting \(1\) more degree, then add an edge between them; if not, it is impossible to satisfy the condition

The tree can be constructed by storing the vertices which wants one degree and two or more degrees, dividing each connected component depending on whether it wants \(1\) degree or \(2\) or more degrees.

Sample code (C++)