5
$\begingroup$

Considering loop free cubic graphs (graphs where every node has 3 neighboring nodes): Is is possible to construct a spanning tree that only has nodes with 3 neighbors in the spanning tree or 1 neighbor in the spanning tree (leaves).

That is I want to be able to construct a spanning tree where there are no nodes that are connected to only 2 other nodes in the spanning tree. They should all be connected to either 1 node (a leaf) or all their edges in the underlying cubic graph should also be present in the spanning tree (ie attached to 3 nodes in the spanning tree)?

Does anyone know the answer to this? And if it is possible, how to construct such a spanning tree? Many thanks.

  • 0
    I'm trying to search for similar questions/results (particularly this question restricted to cubic *polyhedral* graphs) but having trouble finding appropriate search terms. Is there a standard name for this kind of tree? "trivalent tree" seems like it would be a natural name for it, and http://mathworld.wolfram.com/CayleyTree.html seems to confirm it, but unfortunately http://mathworld.wolfram.com/TrivalentTree.html seems to contradict it (allowing vertices of degree 2). Confusing.2016-06-26

1 Answers 1

4

It's not always possible. For example:

Counter-example