微科普之Necessary and sufficient condition for a sequence to be graphic

This proof is due to Choudum.

A sequence of nonnegative integers (d_1,...,d_n) is called graphic if there is a simple graph G with V(G)=\lbrace v_1,...,v_n\rbrace and d(v_i)=d_i. It's very easy to show that if a nonincreasing sequence, i.e. d_1\ge d_2\ge...\ge d_n is graphic then \sum_{i=1}^n d_i is even and \forall 1\le k\le n we have

\sum_{i=1}^k d_i\le k(k-1)+\sum_{i=k+1}^n \min\lbrace k,d_i\rbrace

In 1960 Erdos and Gallai showed that this condition is also sufficient, whose proof is yet very complicated. In 1986, however, Choudum discovered a very simple proof, actually simple as an Olympiad problem for junior high, using an extraordinary induction. Here we present it to those who are curious about how easy this seemingly monstrous problem can be.

We proceed by inducting on x={1\over 2}\sum_{i=1}^n d_i. When x=0 the sequence is trivially graphic. Suppose it holds for x=k, when x=k+1, without losing generality assuming d_n\ge 1. Let t be the smallest index s.t. d_t>d_{t+1}; when d_1=...=d_n set t=n-1. We show (d_1',...,d_n')=(d_1,...,d_{t-1},d_t-1,d_{t+1},...,d_{n-1},d_n-1), satisfies the inequalities and hence graphic by induction hypothesis. Shortly we will see that such choice of t is really a wise move.

If k\ge t, it's easy to see \min\lbrace k,d_n\rbrace-1\le\min\lbrace k,d_n-1\rbrace by case distinguishing, therefore

\sum_{i=1}^k d_i'=\sum_{i=1}^{k} d_i-1\le k(k-1)+\sum_{i=k+1}^n \min\lbrace k,d_i\rbrace-1\le k(k-1)+ \sum_{i=k+1}^n \min\lbrace k,d_i'\rbrace

If k\le t-1, but d_n-1\ge k, the result and the condition are identical. When d_n\le k, if d_1\le k-1, we have

\sum_{i=1}^k d_i'=kd_1\le k(k-1)

so the inequality holds as all terms added are positive, and if d_1=k,

kd_1=k(k-1)+k-1+1=k(k-1)+\min\lbrace k,d_t-1\rbrace+1

The only case this fails to the inequality we want is that d_n=1 and [k,t-1]=[t+1,n]=\emptyset, namely the original sequence is d_1=...=d_{t}=k, d_{t+1}=1, where t+1=n and t-1=k. Yet in this case we have \sum_{i=1}^n d_i=k(k+1)+1, an odd number, contradiction.

Hence we consider the case when d_1\ge k+1. Then d_t-1=d_1-1\ge k, so we just need to prove it cannot be the case that

kd_1=\sum_{i=1}^k d_i=k(k-1)+\sum_{i=k+1}^n \min\lbrace k,d_i\rbrace

If it is, assume j is the largest index s.t. d_j\ge k+1. Then t\le j\le n-1 as d_t=d_1\ge k+1 and d_n\le k. Then we have

d_1=(k-1)+{1\over k}\sum_{i=k+1}^j k+{1\over k}\sum_{i=j+1}^n d_i=j-1+{1\over k}\sum_{i=j+1}^n d_i

Here comes the second fascinating part of this proof. Since d_j\ge k+1, \min\lbrace k+1,d_i\rbrace=k+1 for i\le j, so consider the original inequality for k+1. As k+1\le t, and \sum_{i=j+1}^nd_i>0 since j+1\le n, we have

\sum_{i=1}^{k+1}d_i=(k+1)d_1=(k+1)(j-1)+{k+1\over k}\sum_{i=j+1}^n d_i>k(k+1)+\sum_{i=k+2}^n \min\lbrace k+1,d_i\rbrace

contradiction.