Remark: let be the set of verices of if has this property that no two vertices in are adjacent, then this is because if then and so

a vertex in can be adjacent to at most vertices, which contradicts regularity of

now label the colors with and for any let be the set of all vertices in colored then clearly and for any also by the above

remark for all therefore: Q.E.D.