K 4 − ‐factor in a graph

Let G be a graph of order 4 k and let δ( G ) denote the minimum degree of G . Let F be a given connected graph. Suppose that | V ( G )| is a multiple of | V ( F )|. A spanning subgraph of G is called an F ‐factor if its components are all isomorphic to F . In this paper, we prove that if δ( G )≥5/2 k , then G contains a K 4 − ‐factor ( K 4 − is the graph obtained from K 4 by deleting just one edge). The condition on the minimum degree is best possible in a sense. In addition, the proof can be made algorithmic. © 2002 John Wiley & Sons, Inc. J Graph Theory 39: 111–128, 2002