A short proof of Kundu's k-factor theorem (Q1106246)

This note gives a very short proof of the k-factor theorem due to \textit{S. Kundu} [Discrete Math. 6, 367-376 (1973; Zbl 0278.05115)]: Theorem. Let \((d_ 1,d_ 2,...,d_ n)\) and \((d_ 1-k_ 1,d_ 2-k_ 2,...,d_ n-k_ n)\) be two graphical sequences satisfying \(k\leq k_ i\leq k+1\), \(1\leq i\leq n\), for some \(k\geq 0\). Then there exists a graph \(G=(V,E)\) which contains a subgraph F such that \(d_ G(v_ i)=d_ i\) and \(d_ F(v_ i)=k_ i\) for all \(v_ i\in \{v_ 1,v_ 2,...,v_ n\}=V(G).\) The above theorem was conjectured by \textit{A. R. Rao} and \textit{S. B. Rao} [J. Comb. Theory, Ser. B 13, 185-191 (1972; Zbl 0224.05126)] for the case \(k_ i=k\) for all i, and independently by B. Grünbaum for the special case \(k_ i=1\) for all i. The proof in this note readily extends to derive the generalizations of the k-factor Theorem obtained by Kundu, Kleitman and Wang, and also provides us with a simple algorithm for constructing the graph G in the theorem. The results for directed graphs may be proved similarly. \{Remark: Lemma 1 is not really necessary in the proof, but it is of some independent interest.\}