Does each graph of minimum degree three admit a spanning tree whose vertices have degree three (exactly) except the leaves (degree one)?
2
-
2$\begingroup$ I guess you mean connected graph of minimum degree $3$; non-connected graphs don't have spanning trees. If every vertex of the spanning tree has odd degree ($1$ or $3$), the number of vertices must be even by the "handshake" lemma. For a counterexample to your question, take any connected graph of minimum degree $3$ with an odd number of vertices, say $K_5-e$. By the way, your question is off topic for this site, next time try math.stackexchange.com. $\endgroup$– bofCommented Dec 1, 2013 at 1:39
-
$\begingroup$ It's even false for regular connected graphs of degree three; there is a counterexample with ten vertices. $\endgroup$– Richard StanleyCommented Dec 1, 2013 at 2:00
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
No graph with an odd number of vertices can have all degrees odd so any connected graph with an odd number of vertices and minimum degree $3$ is a counterexample.
There are at least two $8$ vertex counter examples which are regular of degree $3$. One is the skeleton of a cube and another is drawn below. In either case a spanning tree would use $7$ edges so the degrees would be eight values with total sum $14.$ This would have to be $3+3+3+1+1+1+1+1$ if no vertices had degree $2$. It is pretty easy to see that this can not be done. 
answered Dec 1, 2013 at 9:48
$\begingroup$
$\endgroup$
The answer is no.
Consider the following construction:
Take $4$ disjoint copies of $K_3$ and add a new special vertex and connect it to every other vertex. You get a graph $G$ on $13$ vertices and $24$ edges. The special vertex has a degree of $12$ and every other vertex has a degree of $3$ in $G$. But, in any tree of $G$ the special vertex has degree of at least $4$.
