Packing two copies of a sparse graph into a graph with restrained maximum degree

We show that if a tree T is not a star, then there is an embedding σ of T in the complement of T such that the maximum degree of T∪σ(T) is at most Δ(T)+2. We also show that if G is a graph of order n with n?1 edges, then with several exceptions, there exists an embedding σ of G in the complement of G such that the maximum degree of G∪σ(G) is at most Δ(G)+3. Both results are sharp in the sense that neither of Δ(T)+2 and Δ(G)+3 can be reduced. From these two results, we deduce two corollaries on packings of three graphs. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 178–187, 2009