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

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Not all cubic graphs have such a spanning tree. $\endgroup$
    – Tyson Williams
    Commented Nov 1, 2012 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
    Commented Nov 1, 2012 at 3:59
  • 2
    $\begingroup$ I constructed an example. It is simple. You can also conduct such an example. $\endgroup$
    – Tyson Williams
    Commented Nov 1, 2012 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
    Commented Nov 1, 2012 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
    Commented Nov 1, 2012 at 12:12

1 Answer 1

Reset to default
5
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ Yes, this is essentially what I thought of. $\endgroup$
    – Tyson Williams
    Commented Nov 1, 2012 at 12:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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