# If $G$ is a tree and $\forall v_1, v_2 : dist(v_1, v_2)$ is even, where $v_1, v_2-$ are leaves $\Rightarrow \exists!$ a maximal independent set.

If $G$ is a tree and $\forall v_1, v_2 : dist(v_1, v_2)$ is even, where $v_1, v_2-$ are leaves of the tree $\Rightarrow \exists!$ a maximal independent set.

Give some clue please!

Thanks anyway!

-

## 1 Answer

Use induction on the number $n$ of nodes. Select a leave $v$ and let $w$ be its unique neighbour.

Case (i): If the degree of $w$ is $>2$, let $G'$ be the tree obtained by removing $v$ from $G$.

Case (ii): If the degree of $w$ is $=2$, let $G'$ be the tree obtained from $G$ by removing both $v$ and $w$.

Case (iii): The case that $w$ has degree 1 is not possible because that would mean an odd distance between leaves $v$ and $w$.

Note that the resulting tree $G'$ is smaller ($n-1$ or $n-2$ nodes) and also has the even leave distance property. By induction, we may assume that there is a unique maximal independent set $I'$ of $G'$ and that it contains all nodes of even distance from all leaves of $G'$ (thus in case (i), $w\notin I'$). Then $I=I'\cup \{v\}$ is an independent set of the original $G$. Assume $J$ is an independent set of $G$ with $|J|\ge |I|$. Then $J'=J\cap G'$ is an independent set of $G'$. Since $J\setminus J'\subseteq \{v,w\}$ but we cannot have both $v\in J$ and $w\in J$, we see that $|J'|\ge |J|-1=|I'|$, hence by induction assumption $J'=I'$. In case (ii), note that $w$ has some neighbour $u$ in $G'$. Since $u$ has distance 2 to leave $v$ in $G$, it has even distance to all leaves in $G'$, hence $u\in I'\subseteq J$ and $w\notin J$. In case (i) we find immediately that $w\notin J$ from $w\notin I'$. Therefore, $|J|\ge |I|>|I'|=|J'|$ implies $J = J'\cup \{v\}=I'\cup \{v\}=I$.

-
Yep, but how do you can assume by induction that it is unique and the most set. I'm sorry for my stupid mind, but using this, I can not say exactly that this is a maximum, and no other. –  jofisher Oct 25 '12 at 22:05
@jofisher: Maybe now? –  Hagen von Eitzen Oct 26 '12 at 6:27
Yep. This is perfect. Thank you very much. –  jofisher Oct 26 '12 at 16:23