Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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$.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.