Let's restate the evil theorem:

If we have an integer N ≥ 2, along with N more integers d₁, d₂, ..., d_N where 1 ≤ d_i for all i and , then there exists a tree T with labeled vertices v₁, v₂, ..., v_N such that vertex v_i has degree d_i.

The proof is by induction.

When N = 2, we have 1 ≤ d_i ≤ N - 1 = 1 for all i, and hence the only possible tuple of d_i's is (1, 1). Clearly there exists such tree T: simply draw a single edge connecting two vertices v₁, v₂. The degree of both v₁ and v₂ is 1, so we have proved the base case.

Now suppose that for some N = K, K ≥ 2, the statement is true. We will prove that the statement is also true for N = K + 1.

Observe that there is some d_i that is equal to 1. If not, then we need to have 2 ≤ d_i for all i, but then their sum is since there are K + 1 numbers, each of which is at least 2, while on the other hand we know that , contradiction. Without loss of generality, suppose d_K + 1 = 1, otherwise just relabel everything.

Also, similarly, there must be some d_i that is not equal to 1. If not, then all of them are equal to 1, and thus their sum is , while on the other hand we know that . These two can only be equal when K = 1, but we assumed K ≥ 2, so this is wrong. Still without loss of generality, suppose d₁ > 1.

Now we draw an edge between v₁ and v_K + 1. This satisfies the degree requirement for v_K + 1, so we may remove it and d_K + 1, and reduce d₁ by 1 into d₁' = d₁ - 1, since v₁ has connected with one vertex and so only needs d₁ - 1 more. Now observe that we are left with K integers, all of them are positive (d₁' is still positive since d₁ > 1 and so d₁ - 1 > 0), and their sum is 2K - 2 (since we subtracted d_K + 1 = 1 from the sum, as well as 1 from d₁ becoming d₁', thus subtracting 2 from 2(K + 1) - 2 giving 2K - 2). Thus by our induction hypothesis, there exists a tree connecting v₁, v₂, ..., v_K. Adding back the edge between v₁ and v_K + 1 completes the construction of our desired tree, and thus the claim holds for N = K + 1.

Since we have proved the base case and the inductive case, by mathematical induction we're done; the evil theorem is true.

So the evil theorem also says that 1 ≤ d_i ≤ N - 1, not only 1 ≤ d_i. But this is immediate: if any of the d_i exceeds N - 1, then the remaining sum will be less than (2N - 2) - (N - 1) = N - 1, and thus we have N - 1 numbers adding to less than N - 1. Clearly some number is going to be lower than 1, contradiction. Thus the upper bound is automatically fulfilled.