Embedding Arbitrary Graphs of Maximum Degree Two

Abstract

Let δ(H) be the minimum degree of the graph H. We prove that a graph H of order n with δ(H) ⩾ (2n−1)/3 contains any graph G of order at most n and maximum degree Δ(G) ⩽ 2 as a subgraph, and this bound is best possible. Furthermore, this result settles the case Δ(G) = 2 of the well-known conjecture of Bollobás, Catlin and Eldridge on packing two graphs with given maximum degree.