Subdivisions of graphs: A generalization of paths and cycles Original Research Article

One of the basic results in graph theory is Diracʹs theorem, that every graph of order image and minimum degree image is Hamiltonian. This may be restated as: if a graph of order n and minimum degree image contains a cycle C then it contains a spanning cycle, which is just a spanning subdivision of C. We show that the same conclusion is true if instead of C, we choose any graph H such that every connected component of H is non-trivial and contains at most one cycle. The degree bound can be improved to image if H has t components that are trees. We attempt a similar generalization of the Corrádi–Hajnal theorem that every graph of order image and minimum degree image contains k disjoint cycles. Again, this may be restated as: every graph of order image and minimum degree image contains a subdivision of image. We show that if H is any graph of order n with k components, each of which is a cycle or a non-trivial tree, then every graph of order image and minimum degree image contains a subdivision of H.