Originators: Hoffman and Ostenhof (presented by A. Kostochka - REGS 2009)
Background: We seek good spanning trees in graphs. For example, one may seek a large or a small number of leaves, small diameter, etc.
Conjecture: Every 3-regular graph G has a spanning tree T such that G-E(T) consists of isolated vertices, isolated edges, and cycles.
Comments: The cycles pass through the leaves of T; the point is that a leaf of T must not be adjacent to a vertex having degree 2 in T. Such trees exist for the Peterson graph, prisms over cycles, and many other graphs that have been tried.