# Cubic (3-regular) graph spanning tree

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.

• Not all cubic graphs have such a spanning tree. Nov 1, 2012 at 3:58
• How do you know for sure? Is there a proof or a citation to something that proves it? Thanks! Nov 1, 2012 at 3:59
• I constructed an example. It is simple. You can also conduct such an example. Nov 1, 2012 at 4:05
• Can you show me the example? If I thought it was that simple I wouldn't be asking the question here. Nov 1, 2012 at 4:20
• The question is more difficult when you don't know which way the answer goes but becomes much easier when I tell you that not all graphs have such a spanning tree. Nov 1, 2012 at 12:12

Here is a counterexample, which I'm too lazy to draw. Let $G_1,G_2$ be diamonds, graphs on four vertices having five of the six edges. Connect matching vertices in $G_1$ and $G_2$ so that you get a connected cubic graph. It seems that there is no spanning tree in which every internal vertex has degree exactly $3$.

• Yes, this is essentially what I thought of. Nov 1, 2012 at 12:10