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.

  • 1
    $\begingroup$ Not all cubic graphs have such a spanning tree. $\endgroup$ – Tyson Williams Nov 1 '12 at 3:58
  • $\begingroup$ How do you know for sure? Is there a proof or a citation to something that proves it? Thanks! $\endgroup$ – tree-hacker Nov 1 '12 at 3:59
  • 2
    $\begingroup$ I constructed an example. It is simple. You can also conduct such an example. $\endgroup$ – Tyson Williams Nov 1 '12 at 4:05
  • $\begingroup$ Can you show me the example? If I thought it was that simple I wouldn't be asking the question here. $\endgroup$ – tree-hacker Nov 1 '12 at 4:20
  • 1
    $\begingroup$ 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. $\endgroup$ – Tyson Williams Nov 1 '12 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$.

| cite | improve this answer | |
  • $\begingroup$ Yes, this is essentially what I thought of. $\endgroup$ – Tyson Williams Nov 1 '12 at 12:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.