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?
Best Answer
If I am not mistaken, and if I understand you correctly, it seems to me that you are right.
The following statement is true.
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.