Proof of the Bollobas-Catlin-Eldridge conjecture

We say that two graphs G and H
pack if G and H can be embedded into the same vertex set such that the
images of the edge sets do not overlap. Bollobas and Eldridge, and
independently Catlin conjectured that if the graphs G and H on n
vertices with maximum degree M(G) and M(H), respectively, satisfy (M(G)
+ 1)(M(H) + 1) d n + 1 then G and H pack.

Aigner and Brandt and, independently, Alon and Fischer proved this in
the case M(G),M(H) < 3, Csaba, Shokoufandeh and Szemeredi proved the
conjecture if M(G),M(H) < 4. Bollobas, Kostochka and Nakprasit settled
the case when one of the graphs is degenerate. Kaul, Kostochka and Yu
showed that if M(G)M(H) < 3/5n and the maximal degrees are large enough
then G and H pack. We prove the conjecture for graphs with at least 10^8
vertices.