Balanced caterpillars of maximum degree 3 and with hairs of arbitrary length are subgraphs of their optimal hypercube
Burkhard Monien, Gerd Wechsung · Journal of Graph Theory · 2017
Abstract A caterpillar is a tree having a path that contains all vertices of of degree at least 3. We show in this article that every balanced caterpillar with maximum degree 3 and 2n vertices is a subgraph of the n‐dimensional hypercube. This solves a long‐standing open problem and generalizes a result of Havel and Liebl (1986), who considered only such caterpillars that have a path containing all vertices of degree at least 2.