Search

Let Kr+1 be the complete graph on r+1 vertices. Rao proved that a non-increasing sequence (d1,d2,…,dn) of nonnegative integers with dr+1≥r has a realization containing Kr+1 as a subgraph if and only if ∑i=1ndi is even and ∑i=1sdi+∑i=1tdr+1+i≤(s+t)(s+t−1)+∑i=s+1r+1min{s+t,di−r+s}+∑i=r+t+2nmin{s+t,di} for all s and t with 0≤s≤r+1 and 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.