3
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ Mar 25, 2022 at 11:01

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – ZZP
    Mar 26, 2022 at 7:45
  • $\begingroup$ 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$. $\endgroup$
    – kabenyuk
    Mar 26, 2022 at 8:39

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.