A short constructive proof of A.R. Raos characterization of potentially Kr+1 K r + 1 -graphic sequences ?
Let Kr+1 K r + 1 be the complete graph on r+1 r + 1 vertices. Rao proved that a non-increasing sequence (d1,d2,,dn) ( d 1 , d 2 ,  , d n ) of nonnegative integers with dr+1?r d r + 1 ? r has a realization containing Kr+1 K r + 1 as a subgraph if and only if ? i = 1 n d i is even and ? i = 1 s d i + ? i = 1 t d r + 1 + i ? ( s + t ) ( s + t ? 1 ) + ? i = s + 1 r + 1 min { s + t , d i ? r + s } + ? i = r + t + 2 n min { s + t , d i } for all s s and t t with 0?s?r+1 0 ? s ? r + 1 and 0?t?n?r?1 0 ? t ? n ? r ? 1 . In this paper, we give a short constructive proof of this characterization that can be implemented as an algorithm to construct a realization containing Kr+1 K r + 1 .
complete graph graphic sequence a.r. raos characterization