# Property of the spanning tree with minimal leaves

Let $$G$$ be a connected simple graph. For any spanning tree $$T$$ of $$G$$, let $$l(T)$$ be the number of leaves of the graph $$T$$. Consider $$\ell=\min_Tl(T)$$, can I find a spanning tree $$T$$ with $$l(T)=\ell$$, such that the set of leaves $$A$$ of $$T$$ is very close to an independent set.

For example, I guess that there exists a vertex $$a\in A$$ such that $$A\setminus\{a\}$$ is an independent set in the graph $$G$$.

My idea is that maybe we can justifying the tree $$T$$ step by step to get a extreme tree with some properties.

Is there any results or references for this question?

• If there are at least two vertices, $\ell = 2$ iff there's a Hamiltonian path, so finding a spanning tree which achieves $\ell$ is NP-hard. Mar 25, 2022 at 11:01

If I am not mistaken, and if I understand you correctly, it seems to me that you are right.

The following statement is true.

Let $$G$$ be a connected graph and $$T$$ be the spanning tree with the smallest number of leaves and $$\ell=l(T)$$. Let $$A$$ be the set of all leaves of tree $$T$$. If $$|A|=\ell>2$$, then $$A$$ is an independent set of graph $$G$$.

Here is a brief proof. Let $$x$$ and $$y$$ be two leaves and $$e=xy$$ be an edge of graph $$G$$. Then the graph $$H=T+e$$ has a cycle. Denote this cycle by $$C$$. If all vertices of the cycle $$C$$ have degree $$2$$ in $$H$$, then $$C=H$$ and our graph $$G$$ is Hamiltonian, and this contradicts the condition $$\ell>2$$.

Hence there exists a vertex $$a$$ of cycle $$C$$ of degree $$3$$ or more in $$H$$. Let $$e'=ab$$ be an edge of $$C$$. The graph $$T'=H-e'$$ is a spanning tree of graph $$G$$ and $$l(T')<\ell$$. Contradiction.

• Thank you for your answer! The graph $H$ have $\ell-2$ leaves, and by deleting $e'$ the leaf number would at most +1 in $T'$, a contradiction.
– ZZP
Mar 26, 2022 at 7:45
• You can also clarify it this way. If $\operatorname{deg}_H(b)>2$, then $l(T')=\ell-2$; if $\operatorname{deg}_H(b)=2$, then $l(T')=\ell-1$. Mar 26, 2022 at 8:39