Decomposing graphs under degree constraints

Abstract

We prove a conjecture of C. Thomassen: If s and t are non-negative integers, and if G is a graph with minimum degree s + t + 1, then the vertex set of G can be partitioned into two sets which induce subgraphs of minimum degree at least s and t, respectively. © 1996 John Wiley & Sons, Inc.