<p>Here is a counterexample, which I'm too lazy to draw. Let $G_1,G_2$ be <em>diamonds</em>, 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$.</p>

CC BY-SA 3.0
2012-11-01T12:10:46.987Z
Yes, this is essentially what I thought of.
Tyson Williams
CC BY-SA 3.0
2012-11-01T05:19:31.640Z
2012-11-01T05:19:31.640Z
Yuval Filmus
<p>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).</p>

<p>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)?</p>

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

CC BY-SA 3.0
2012-11-01T03:58:49.497Z
Not all cubic graphs have such a spanning tree.
Tyson Williams
CC BY-SA 3.0
2012-11-01T03:59:53.677Z
How do you know for sure? Is there a proof or a citation to something that proves it? Thanks!
tree-hacker
CC BY-SA 3.0
2012-11-01T04:05:15.327Z
I constructed an example. It is simple. You can also conduct such an example.
Tyson Williams
CC BY-SA 3.0
2012-11-01T04:20:29.923Z
Can you show me the example? If I thought it was that simple I wouldn't be asking the question here.
tree-hacker
CC BY-SA 3.0
2012-11-01T12:12:40.373Z
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.
Tyson Williams
<ds.algorithms><graph-theory><graph-algorithms><tree>
Cubic (3-regular) graph spanning tree
tree-hacker
# Cubic (3-regular) graph spanning tree

(Asked by: username_0 on 2012-11-01)

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.

**Tags:** ds.algorithms, graph-theory, graph-algorithms, tree
> **Comments:**
> **username_1**: Not all cubic graphs have such a spanning tree.  
> **username_0**: How do you know for sure? Is there a proof or a citation to something that proves it? Thanks!  
> **username_1**: I constructed an example. It is simple. You can also conduct such an example.  
> **username_0**: Can you show me the example? If I thought it was that simple I wouldn't be asking the question here.  
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2012-11-01. Score: 5

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$.

> **Comments:**
> **username_1**: Yes, this is essentially what I thought of.  

---

