I'm trying to prove by induction that for all trees of order $n$ ($n\geq 2$), the star of order $n$ has the largest number of independent vertex sets.
I've started this by showing that $n=2$ and $n=3$ are trivial, then assuming $n$ is true. Then let $G$ be a tree of order $n+1$. I'm considering an endpoint $v$, and what would happen when removing v, but getting stuck. I've read a proof by Prodinger and Tichy but don't understand it, and wondering if there is another way.
My thoughts are that by removing the leaf (endpoint) from $G$, we are left with a tree of order $n$, so we know the max. no. of sets is achieved by the star. But I can't quite get to the idea of finishing the proof. Thanks!
Yes, I think an inductive argument works. Write $I(T)$ for the number of independent sets. Let $v$ be a leaf of $T$, adjacent to a vertex $w$, and consider $I(T-v)$. Now $I(T)=2I(T-v)-k$, where $k$ is the number of independent sets of $T-v$ that contain $w$ (since these are the sets that would stop being independent if you add $v$). Note that $k\geq1$, with equality if and only if $w$ is adjacent to every other vertex of $T-v$, i.e. it is the centre vertex of a star. Also $I(T-v)$ is maximised when $T-v$ is a star (by the induction hypothesis). Putting this together, you get that $I(T)$ is maximised when $T-v$ is a star and $v$ was adjacent to the centre of that star, i.e. $T$ is also a star.