Let $S=\{s_1,\ldots,s_\ell\}$ be the independent set of vertices, so we know $\ell \ge \tfrac{n+k-1}{2}$. Define $E_i$ to be the set of edges which have $s_i$ as a vertex, for all $i$. Note $E_i\cap E_j=\emptyset$ for any $i$ and $j$, since if $e\in E_i$ and $e\in E_j$, then $e=s_is_j$, contradicting $S$ independent. Now, since $T$ has $n-1$ edges, \[ n-1\ge |E_1\cup \cdots \cup E_\ell| = |E_1|+\cdots+|E_\ell| = \sum_{i=1}^\ell \deg s_i. \]Clearly $n\ge k$, so $\ell\ge \tfrac{n+k-1}{2}\ge \tfrac{k+(k-1)}{2} = k-\tfrac12$, so $\ell\ge k$. Suppose $a$ of the elements of $S$ are leaves of $T$. Then all other vertices of $S$ have degree at least $2$, so \[ \sum_{i=1}^\ell \deg s_i \ge 1\cdot a + 2\cdot (\ell-a) = 2\ell-a \ge 2\ell-k \ge 2\left(\frac{n+k-1}{2}\right)-k=n-1.\]Combining the two inequality chains, we conclude that equality must be achieved in all bounds. Therefore, $E_1\sqcup \cdots \sqcup E_\ell=E$, the entire edge set of $T$, since $n-1=|E_1\cup \cdots \cup E_\ell|$. All leaves of $T$ are elements of $S$, since $a=k$. Claim: If we color all vertices of $S$ red, and all vertices of $E\setminus S$ blue, this forms a $2$-coloring of $T$. Proof: It is well-known that trees are $2$-colorable. By (i), all edges of $T$ have red-blue endpoints. In particular, there are no blue-blue or red-red edges. $\blacksquare$ By (ii), all leaves are in $S$, so by the Claim, all leaves are the same color in the $2$-coloring. Therefore, any path between two leaves has even distance. It is clear (say by rooting the tree) that the longest path of $T$ will be between $2$ leaves, so we are done.

My problem The motivation came from trying to find all possible values of the size of the largest independent set in a tree with $n$ vertices and $k$ leaves. The intuition here is that picking “every other vertex” gives you $\approx \frac{n}{2}$ vertices. Depending on the parities of the distances between the leaves you might be able to add some extra leaves to your independent set, increasing the size of the independent set by a number between $0$ and $\frac{k}{2}$; using this intuition it’s then possible to formally show that the size of the independent set is always at most $\frac{n+k-1}{2}$. Examining the equality case then makes it clear that any two leaves have even distance between them, from which the result follows.

Claim 1: Let $f(T)$ be the size of the largest pairwise nonadjacent subset of $T$. Then \[f(T)\leq \frac{n+k-1}{2}\]Proof: Strong induction on $n$. The base cases $n=2$ and $n=3$ are uniquely defined, we have $f(T_2) = 1< \frac{2+2-1}{2}$ and $f(T_3) = 2 \leq \frac{3+2-1}{2}$. For the inductive step, note that there always exists some leaf $L$ which is only connected to $M$, we do casework on $\deg M$. Case 1: $\deg M=2$. Thus, if we remove $L$ from $T$, then $M$ will be a leaf. To induct, let $T'$ be the graph gotten from removing $L$ and $M$. Then, \[f(T) \leq f(L+M) + f(T') = 1 + f(T') \leq 1 + \frac{(n-2)+k-1}{2} = \frac{n+k-1}{2}.\]where the last $\leq$ comes from the fact that $T'$ can have at most $k$ leaves, so $M$'s sole other neighbor $N$ must become a leaf. Case 2: $\deg M = 3$. This time we let $T'$ be the graph gotten from removing just $L$, then \[f(T) \leq f(L) + f(T') \leq 1 + \frac{(n-1)+ (k-1)-1}{2} = \frac{n+k-1}{2}\]where equality occurs when $M$ is not colored in $T'$'s optimal coloring. Thus, the induction is complete. $\square$. Claim 2: The equality case of Claim 1 occurs only when the path between each pair of leaves is "on off on off ... off on" included in $f(T)$. Proof: Induction. $T_2$ does not satisfy the equality case, so if $T$ satisfies $f(T) = \frac{n+k-1}{2}$, then $T$ reduces to $T_3$, and $T_3$ is our base case that has coloring "on off on". For the inductive step. We use the same cases as before Case 1: $\deg M=2$. We remove two leaves, and the equality case only occurs when that leaves the leaf $N$, which means that the pattern clearly still holds. Case 2: $\deg M = 3$. We remove $N$, and by the inductive hypothesis since $M$ is not included in $f(T')$, we have that $M$ is an odd distance from each of the other leaves, so $N$ will merely be added on to the end of the on off on sequences. $\square$. Thus, we have fully characterized all trees $T$ which have some subset of at least $\frac{n+k-1}{2}$ vertices which are pairwise nonadjacent, and since the path between each pair of leaves has an even number of edges, clearly the length of the longest path in $T$ also has an even number of edges and we're done. $\blacksquare$.

I'm very confused, can someone check whether this is a fakesolve? Let $B$ be the longest path in $T$, and let $S$ be the set of at least $\tfrac{n+k-1}{2}$ vertices. Start from a leaf not on $B$, and walk to its neighbor $v_1$. If $\text{deg}(v_1)=2$ then walk to the other neighbor $v_2$ of $v_1$, and so on, until you reach a vertex of degree $\ge 3$. Call the path obtained through this walk a branch. The below diagram shows all the branches in an example. [asy][asy] /* Geogebra to Asymptote conversion, documentation at artofproblemsolving.com/Wiki go to User:Azjps/geogebra */ import graph; size(10cm); real labelscalefactor = 0.5; /* changes label-to-point distance */ pen dps = linewidth(0.7) + fontsize(10); defaultpen(dps); /* default pen style */ pen dotstyle = black; /* point style */ real xmin = -11.852967780409013, xmax = 0.8904095419352241, ymin = -3.661960318808306, ymax = 4.10999620447981; /* image dimensions */ pen ccqqqq = rgb(0.8,0,0); /* draw figures */ draw((-1,1)--(-11,1), linewidth(1)); draw((-9,1)--(-9.275340395256398,0.11285896998006113), linewidth(1) + ccqqqq); draw((-9,1)--(-8.670014021651108,0.1035529586933725), linewidth(1) + ccqqqq); draw((-7,1)--(-6.976644380217993,0.13139684106908053), linewidth(1)); draw((-6.976644380217993,0.13139684106908053)--(-7.273250317642304,-0.5359665181356172), linewidth(1) + ccqqqq); draw((-7.273250317642304,-0.5359665181356172)--(-7.588394126155634,-1.1847920062512958), linewidth(1) + ccqqqq); draw((-6.976644380217993,0.13139684106908053)--(-6.624424829526625,-0.5452354536801269), linewidth(1) + ccqqqq); draw((-6.624424829526625,-0.5452354536801269)--(-6.272205278835256,-1.2311366839738442), linewidth(1) + ccqqqq); draw((-6.272205278835256,-1.2311366839738442)--(-5.8559651903379635,-2.047766981187328), linewidth(1) + ccqqqq); draw((-4,1)--(-3.9901284652281612,0.052573813198569165), linewidth(1)); draw((-3.9901284652281612,0.052573813198569165)--(-4.3367866545928235,-0.6101550782338742), linewidth(1) + ccqqqq); draw((-4.3367866545928235,-0.6101550782338742)--(-4.724228160353329,-1.283079798765278), linewidth(1) + ccqqqq); draw((-3.9901284652281612,0.052573813198569165)--(-3.5822953012697343,-0.6203509073328348), linewidth(1) + ccqqqq); /* dots and labels */ dot((-1,1),dotstyle); dot((-11,1),dotstyle); dot((-10,1),dotstyle); dot((-9,1),dotstyle); dot((-8,1),dotstyle); dot((-7,1),dotstyle); dot((-6,1),dotstyle); dot((-5,1),dotstyle); dot((-4,1),dotstyle); dot((-3,1),dotstyle); dot((-2,1),dotstyle); dot((-9.275340395256398,0.11285896998006113),dotstyle); dot((-8.670014021651108,0.1035529586933725),dotstyle); dot((-6.976644380217993,0.13139684106908053),dotstyle); dot((-7.273250317642304,-0.5359665181356172),dotstyle); dot((-7.588394126155634,-1.1847920062512958),dotstyle); dot((-6.624424829526625,-0.5452354536801269),dotstyle); dot((-6.272205278835256,-1.2311366839738442),dotstyle); dot((-5.8559651903379635,-2.047766981187328),dotstyle); dot((-3.9901284652281612,0.052573813198569165),dotstyle); dot((-4.3367866545928235,-0.6101550782338742),dotstyle); dot((-4.724228160353329,-1.283079798765278),dotstyle); dot((-3.5822953012697343,-0.6203509073328348),dotstyle); clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle); /* end of picture */ [/asy][/asy] We inductively remove branches until only $B$ remains. In particular, note that whenever we delete a branch with $t$ vertices, the $|S|\ge \tfrac{n+k-1}{2}$ condition is still satisfied, since at most $\tfrac{t+1}{2}$ of the vertices in the branch could've been in $S$: \begin{align*} n_{\text{new}}&=n_{\text{old}}-t\\ k_{\text{new}}&=k_{\text{old}}-1\\ |S|_{\text{new}}&\ge |S|_{\text{old}}-\frac{t+1}{2}\\ \implies |S|_{\text{new}} &\ge \frac{n_{\text{new}}+k_{\text{new}}-1}{2}. \end{align*}Eventually, we'll only have $B$ left. Letting $B$ has $p$ vertices, we have $$\frac{p+2-1}{2} \le |S| \le \frac{p+1}{2}$$where the second inequality only has equality when $p$ is odd, as desired.

VulcanForge wrote: I'm very confused, can someone check whether this is a fakesolve? Let $B$ be the longest path in $T$, and let $S$ be the set of at least $\tfrac{n+k-1}{2}$ vertices. Start from a leaf not on $B$, and walk to its neighbor $v_1$. If $\text{deg}(v_1)=2$ then walk to the other neighbor $v_2$ of $v_1$, and so on, until you reach a vertex of degree $\ge 3$. Call the path obtained through this walk a branch. The below diagram shows all the branches in an example. [asy][asy] /* Geogebra to Asymptote conversion, documentation at artofproblemsolving.com/Wiki go to User:Azjps/geogebra */ import graph; size(10cm); real labelscalefactor = 0.5; /* changes label-to-point distance */ pen dps = linewidth(0.7) + fontsize(10); defaultpen(dps); /* default pen style */ pen dotstyle = black; /* point style */ real xmin = -11.852967780409013, xmax = 0.8904095419352241, ymin = -3.661960318808306, ymax = 4.10999620447981; /* image dimensions */ pen ccqqqq = rgb(0.8,0,0); /* draw figures */ draw((-1,1)--(-11,1), linewidth(1)); draw((-9,1)--(-9.275340395256398,0.11285896998006113), linewidth(1) + ccqqqq); draw((-9,1)--(-8.670014021651108,0.1035529586933725), linewidth(1) + ccqqqq); draw((-7,1)--(-6.976644380217993,0.13139684106908053), linewidth(1)); draw((-6.976644380217993,0.13139684106908053)--(-7.273250317642304,-0.5359665181356172), linewidth(1) + ccqqqq); draw((-7.273250317642304,-0.5359665181356172)--(-7.588394126155634,-1.1847920062512958), linewidth(1) + ccqqqq); draw((-6.976644380217993,0.13139684106908053)--(-6.624424829526625,-0.5452354536801269), linewidth(1) + ccqqqq); draw((-6.624424829526625,-0.5452354536801269)--(-6.272205278835256,-1.2311366839738442), linewidth(1) + ccqqqq); draw((-6.272205278835256,-1.2311366839738442)--(-5.8559651903379635,-2.047766981187328), linewidth(1) + ccqqqq); draw((-4,1)--(-3.9901284652281612,0.052573813198569165), linewidth(1)); draw((-3.9901284652281612,0.052573813198569165)--(-4.3367866545928235,-0.6101550782338742), linewidth(1) + ccqqqq); draw((-4.3367866545928235,-0.6101550782338742)--(-4.724228160353329,-1.283079798765278), linewidth(1) + ccqqqq); draw((-3.9901284652281612,0.052573813198569165)--(-3.5822953012697343,-0.6203509073328348), linewidth(1) + ccqqqq); /* dots and labels */ dot((-1,1),dotstyle); dot((-11,1),dotstyle); dot((-10,1),dotstyle); dot((-9,1),dotstyle); dot((-8,1),dotstyle); dot((-7,1),dotstyle); dot((-6,1),dotstyle); dot((-5,1),dotstyle); dot((-4,1),dotstyle); dot((-3,1),dotstyle); dot((-2,1),dotstyle); dot((-9.275340395256398,0.11285896998006113),dotstyle); dot((-8.670014021651108,0.1035529586933725),dotstyle); dot((-6.976644380217993,0.13139684106908053),dotstyle); dot((-7.273250317642304,-0.5359665181356172),dotstyle); dot((-7.588394126155634,-1.1847920062512958),dotstyle); dot((-6.624424829526625,-0.5452354536801269),dotstyle); dot((-6.272205278835256,-1.2311366839738442),dotstyle); dot((-5.8559651903379635,-2.047766981187328),dotstyle); dot((-3.9901284652281612,0.052573813198569165),dotstyle); dot((-4.3367866545928235,-0.6101550782338742),dotstyle); dot((-4.724228160353329,-1.283079798765278),dotstyle); dot((-3.5822953012697343,-0.6203509073328348),dotstyle); clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle); /* end of picture */ [/asy][/asy] We inductively remove branches until only $B$ remains. In particular, note that whenever we delete a branch with $t$ vertices, the $|S|\ge \tfrac{n+k-1}{2}$ condition is still satisfied, since at most $\tfrac{t+1}{2}$ of the vertices in the branch could've been in $S$: \begin{align*} n_{\text{new}}&=n_{\text{old}}-t\\ k_{\text{new}}&=k_{\text{old}}-1\\ |S|_{\text{new}}&\ge |S|_{\text{old}}-\frac{t+1}{2}\\ \implies |S|_{\text{new}} &\ge \frac{n_{\text{new}}+k_{\text{new}}-1}{2}. \end{align*}Eventually, we'll only have $B$ left. Letting $B$ has $p$ vertices, we have $$\frac{p+2-1}{2} \le |S| \le \frac{p+1}{2}$$where the second inequality only has equality when $p$ is odd, as desired. Same solution

Apparently no one's posted this yet, so in the sprit of tastymath's motivation, take any odd path between leaves. Pair up all the vertices on the path into pairs of adjacent ones. Then pair up the rest of the vertices into adjacent pairs in the natural way by greedily extending outwards from our original path. Only at most $k - 2$ leaves will be left as unpaired vertices at the end. Now the size of a non-adjacent subset of vertices is bounded above by the total number of pairs and unpaired vertices. This immediately gives a contradiction.

We present two solutions. First solution by indicator variables (Raymond Feng) Number the vertices 1, 2, \ldots, \(n\), and let \(x_i\) be an indicator varible for whether vertex \(i\) is in the independent subset. Then observe that \[k+n-1\le2\sum_{i=1}^nx_i\le\sum_{\text{leaves}}x_i+\sum_{\text{edges}}(x_u+x_v)\le k+n-1,\]so equality holds. In particular, every leaf is in the independent subset, and every edge contains exactly one endpoint in the independent subset. The endpoints of the longest path are leaves and thus in the independent subset, and along the path, every other vertex is in the independent subset. It follows that the path contains an even number of edges. Second solution by induction We prove the following: Claim: In a tree \(T\) with \(n\) vertices and \(k\) leaves, each independent subset \(I\) has size at most \(\frac{n-k+1}2\), with equality if and only if each leaf is in \(I\) and every edge contains exactly one endpoint in \(I\). Proof. We induct on \(n\) and \(k\). If there are two leaves that stem from the same node, we may remove one of them, so the resulting tree \(T'\) has \(n'=n-1\) vertices and \(k'=k-1\) leaves. We have \[|I|\le|I'|+1=\frac{(n-1)+(k-1)-1}2+1=\frac{n+k-1}2,\]with equality if and only if \(I'\) satisfies the conditions and the removed leaf is in \(I\). Else if there is a leaf not in \(I\), remove it. The resulting \(T'\) has \(n'=n-1\), \(k'=k\) (since the parent has only one child by (i)), and \[|I|=|I'|\le\frac{(n-1)+k-1}2<\frac{n+k-1}2.\] Else if there are two adjacent vertices not in \(I\), combine them into one vertex, so the resulting \(T'\) has \(n'=n-1\), \(k'=k\) (since neither is a leaf by (ii)), and \[|I|=|I'|\le\frac{(n-1)+k-1}2<\frac{n+k-1}2.\] Else, take a leaf \(v\) and its parent \(u\), and remove them. Let the other neighbors of \(u\) be \(w_1\), \ldots, \(w_\ell\), and let \(T_i\) be the tree with root \(w_i\) when \(u\) is cut off. Let each \(T_i\) have \(n_i\) vertices, \(k_i\) leaves, and let \(I_i\) be the subset of \(I\) in \(T_i\). Then \[\sum_{i=1}^nn_i=n-2\quad\text{and}\quad\sum_{i=1}^\ell k_i\le k+\ell-1,\]implying \begin{align*} |I|=1+\sum_{i=1}^\ell|I_i|&\le1+\sum_{i=1}^\ell\frac{n_i+k_i-1}2\\ &\le\frac{(n-2)+(k+\ell-1)-\ell}2+1=\frac{n+k-1}2, \end{align*}with equality if and only if \(w_1\), \ldots, \(w_\ell\) are in \(I\) and \(T_1\), \ldots, \(T_\ell\) satisfy the condition. The resulting base cases are trivial, so the claim is proven. \(\blacksquare\) Now if \(|I|=\frac{n+k-1}2\), we know the endpoints of the longest path are in \(I\), and every other vertex on this path is in \(I\). It follows that this path contains an even number of edges, the end.

This solution doesn't use induction. The number $\frac{n+k-1}{2}$ looks maximal. It indeed is. We can in fact categorize all trees of this type. Lemma 1: [Recursive construction of maximal independent set] A maximal independent set of a tree contains all leaves. Proof: One of the leaf and the parent must be chosen. If the parent is chosen, the set of vertices that can be used is a subset of the set if the leaf is chosen. Consider a multi-source BFS from the leaves. Let $S_i$ be the set of vertices with depth $i$ (i.e. the shortest distance between a vertex in $S_t$ and a leaf is $t$). This lemma suggests the maximum independent set has size at most $\sum\limits_{n\ge 0} |S_{2n}|$ Observe $|S_i|\ge |S_{i+1}|$. Why? I can truncate the tree such that $S_i$'s become leaves. Then each leaf maps to a parent, but each parent can correspond to more than one child. Case 1: $\sum\limits_{n\ge 0} |S_{2n+1}| > \sum\limits_{n\ge 0} |S_{2n+2}|$. Then $k+\sum\limits_{n\ge 0} |S_{2n+2}|<k+\frac{n-k}{2}$, as needed. Case 2: $\sum\limits_{n\ge 0} |S_{2n+1}| = \sum\limits_{n\ge 0} |S_{2n+2}|$ This implies that $|S_{2n+1}|=|S_{2n+2}|>0$ for some $n$ st $|S_{2n+3}|=0$. Note the induced subgraph of $S_{2n+2}$ is a tree. If it has one vertex, it is a leaf in the original graph. If it has at least two vertices, I can't pick all of them. This case gives at most $k+\frac{n-k}{2}-1$ vertices, impossible. Repeating the same analysis for case 1 gives $|S_{2n+1}|=1$ and $S_{2k}$ an independent set for all $k$. Therefore, the graph has $|S_{2n+1}|=1$ for some $n$ and for all $k\ge 1, |S_{2k-1}|=|S_{2k}|$. Furthermore, $|S_{2n}|>1$ or the vertex in $S_{2n+1}$ is a leaf. The diameter goes through $S_{2n+1}$ and two of its neighbours and has length $4n+2$, as needed.

I will in fact show that $\frac{n+k-1}{2}$ is the maximum size of an independent set in any tree and the problem is a consequence of analyzing the equality case. First note that for chains, the problem is trivially true. Now induct, consider the maximal path in $T$, and say it is of size $M$. At each node of the tree, there are some "sub-trees" attached, let $n_i, l_i$ be the number of vertices and leaves in each of them. By the inductive hypothesis, each sub-tree has independent set of size at most $\frac{n_i + l_i - 1}{2}$. Consider what happens upon deleting the leftmost subtree (call it $T'$) except for the vertex part of the max path, which I'll call $v$. If $v$ was a leaf of $T'$ and $T'$ achieves the equality case of the bound, then it must have been part of the maximal independent set (otherwise we could have deleted it and obtained a better bound, not possible). Therefore, the number of things of the maximal independent set of $T$ that were deleted is at most $\frac{n_i + l_i - 1}{2} - 1$ in this case. We are left with $n-n_i$ vertices, $k-l_i + 1$ leaves and size of independent set is now $S - \frac{n_i+l_i - 1}{2} + 1$ at most, by the inductive hypothesis, this should have at most $\frac{n+k-n_i - l_i -2}{2}$ vertices size independent set. So we obtain that $S \le \frac{n+k-1}{2}$, as desired, and in particular, since the maximal path of $T-T'$ must also be the maximal path of $T$, we have that this also has an even number of edges. If $v$ was not a leaf of $T'$, then we can proceed similarly except we have $k-l_i$ leaves left and the independent set deleted was size at most $\frac{n_i+l_i-1}{2}$. So this completes the induction and we are done. $\blacksquare$

Observe that in any tree $T$ of $n$ vertices there is atleast 2 and atmost $n$ leaves.So for $2\le k\le n$, let $P(n,k)$ denote the statement that in any tree $T$ of $n$ vertices and $k$ leaves the maximum independent set has size atmost $\frac{n+k-1}{2}$. Claim: $P(n,k)$ is true. Proof. We will prove it by induction on $n+k$.Observe that, $P(n,2)$ is true,since 2 leaves implies the graph is just a path. Now consider a tree with $n$ vertex and $k\ge 3$ leaves.Let $\ell$ be a leaf.Start walkig from $\ell$, $$\ell\to \ell_1\to \ell_2\to\dots \to \ell_r\to f(\ell)$$Where $f(\ell)$ denote the first vertex with degree greater than equal to 3.This $f(\ell)$ must exists since otherwise $T$ would become a path which is not possible by the assumption that $T$ has atleast 3 leaves.Let, $$S=\{\ell,\ell_1,\dots ,\ell_r\}$$Delete $S$ from the vertex set of $T$ to obtain a new tree $T'$.By iduction hypothesis,(since $|S|$ vertices and 1 leaf is deleted),any independent set of $T'$ has size atmost, $\frac{(n-|S|)+(k-1)-1}{2}$.On the other hand in any independent set of $T$ at most $\frac{|S|+1}{2}$ vertex from $S$ can be taken.So any independent set of $T$ can have atmost,$$\frac{(n-|S|)+(k-1)-1}{2}+\frac{|S|+1}{2}=\frac{n+k-1}{2}$$vertices.$\blacksquare$ In the rest of the proof $f(\ell),S,T$ will be used with the same definition of above. Claim: If $S$ is of even size then the upper bound of $\frac{n+k-1}{2}$ can't be acheived. Proof.Indeed,if $|S|$ is even then in any independent set atmost $\frac{|S|}{2}$ vertices from $S$ can be taken.On the other hand maximum independent set of $T-S$ has size at most $\frac{(n-|S|)+(k-1)-1}{2}$.$\blacksquare$ Claim: Let $I$ be independent set of $T$. If $f(\ell)\in I$ then $I< \frac{n+k-1}{2}$ Proof. If $f(\ell)\in I$ then due to odd parity of $|S|$ (by 2nd claim) atmost $\frac{|S|-1}{2}$ vertex from $S$ can be taken in $I$.Again same argument like 2nd claim. $\blacksquare$ Claim: The bound is achieved implies that every leaf is in the independent set, and exactly one endpoint of each edge belongs to that independent set. proof. Again proof by induction.The independent set $I$ of $T$ has size $\frac{n+k-1}{2}$ implies $I\cap (T-S)$ has size $\frac{(n-|S|)+(k-1)-1}{2}$.So by induction hypothesis exactly one vertex adjacent to each edge and each leaf is taken in $I$ from $T-S$. Now in order to take $\frac{|S|+1}{2}$ vertices from $S$,we must have to take $\ell,\ell_2,\ell_4,\dots,\ell_r$.The induction is complete.$\blacksquare$ Finally observe that each path from a leaf to another leaf has even number of edges,hence the maximal path has even number of edges.$\blacksquare$

Let $v_0,...,v_L$ be the vertices of the longest path (or in general of any path between two leaves). For $1\leq i\leq L-1$ let $T_i$ be the graph obtained by cutting the edges $(v_iv_{i-1})$ and $(v_iv_{i+1})$ and considering the vertices connected to $v_i$. Let $L_i$ be the set of leaves of $T_i$ (excluding if necessary $v_i$), and $M_i=T_i-\{v_i\}-L_i$. Also let $t_i,l_i,m_i$ be the cardinalities of $T_i,L_i,M_i$ respectively. Finally let $n_i$ be the size of greatest independent subset $N_i$ of $T_i-\{v_i\}$ minus $L_i$. Lemma: $2n_i\leq m_i$ Proof: Firstly the greatest indipendent subset of $T_i-\{v_i\}$ must include its leaves, because if the node before a leaf $l$ is taken, replacing it by all its leaves is only advantageous. Let $N_i'$ be the set of vertices descending from the nodes of $N_i$. Clearly we have $|N_i|\leq |N_i'|$, $N_i'\cap L_i=\{\}$ and $N_i\cap N_i'=\{\}$, from which follows that $2|N_i|\leq |N_i|+|N_i'|\leq m_i$. Let $A$ be the size of the maximal indipendent subset of $T$. The maximal indipendent subset of the subtree $\{v_0,...,v_L\}$ is clearly $\frac{L}{2}+1$. Therefore, in the total, we have $$A\leq \frac{L}{2}+1+\sum_{i=1}^{L-1}k_i+\sum_{i=1}^{L-1}n_i$$$$\leq \frac{L}{2}+1+k-2+\sum_{i=1}^{L-1}\frac{m_i}{2}$$$$=\frac{L-2+2k+\sum_{i=1}^{L-1}t_i-k_i-1}{2}$$$$=\frac{L-2+2k+n-2-(k-2)-(L-1)}{2}=\frac{n+k-1}{2}$$

Let $ S$ be a set of independent vertices in $ T$ with $ s:=|S|\ge \displaystyle \frac{n+k-1}{2}.$ Thus, we have $$ \displaystyle n\le 2s-k+1\qquad (1)$$Let's thinks of it in the following way. We are given this set $ S$ (see $\textbf{fig. 1}$, the blue dots) and want to reconstruct somehow $ T$ so that $ (1)$ holds. It will be shown that the structure of $ T$ complies to a certain rule, and moreover it's impossible $ (1)$ to be strict inequality, the only way is $ n=2s-k+1.$ Let $ O$ be a vertex of $ T, O\notin S$ and $ O$ is not a leaf of $ T$. Of course, we can choose a vertex like that, for example, take $ v_1,v_2\in S$; there is a unique path that connects $ v_1$ with $ v_2$ and at least one vertex on this path is not in $ S.$ Denote it by $ O.$ We view on $ T$ as a tree with a root $ O.$ Having a root, we can compare the vertices. Let's say a vertex $ u\in V(T)$ is one level up a vertex $ v\in V(T)$ if we can reach $ u$ from $ v$ by one hop off the root $ O$. Let $ L$ be the set of leaves of $ T$. For each $ v\in S\setminus L$ we choose a vertex $ u=\mathrm{up}(v)$ which is one level up $ v.$ For $ v\in S\cap L$ we define $ \mathrm{up}(v)=v.$ ($\textbf{fig.2)}$ Clearly, the sets $ \{v,\mathrm{up}(v)\}, v\in S$ are disjoint. Using $ (1)$ we prove two things. \begin{align*} &\text{i) } \quad \bigcup_{v\in S}\mathrm{up}(v)\cup S\cup \{O\}=V(T). \\ &\text{ii) }\quad \text{All leaves of } T \text{ are in } S. \end{align*}Let $ k_1:=\left|L\cap S\right|.$ So, $ k_1\le k=|L|.$ Note that \begin{align*} \left|\bigcup_{v\in S}\mathrm{up}(v) \cup S\cup\{O\}\right|&=2\left| \setminus L\right|+\left| S\cap L\right|+1\\ &=2(s-k_1)+k_1+1=2s-k_1+1. \end{align*}Using the given condition $ (1)$ we get $$ \displaystyle 2s-k_1+1 \le n \le 2s-k+1 \qquad(2)$$Since $ k_1\le k$ it yields $ k=k_1$ and $ n=2s-k+1.$ That is, there are not other vertices of $ T$ that are outside $ \displaystyle \bigcup_{v\in S}\mathrm{up}(v)\cup S\cup \{O\}$ (which is exactly what i) says) and all leaves of $ T$ are in $ S$ (what ii) claims). So, if we color the vertices of $ S$ with blue and the others in black, the structure of $ T$ is like in the $\textbf{fig. 3.}$ Starting from $ O$, every black vertex can have several upper blue vertices but not a black one and every blue vertex can have only one vertex upper than it and it is a black one. Moreover, the leaves of $ T$ are colored in blue. Thus, any path in $ T$ consists of alternating black and blue vertices. Now, the longest path in $ T$ connects some two leaves, hence it consists of even number of edges. $\textbf{Remark}$. More comments on this problem and motivation behind can be found in my blog.

Let $S$ be the independent set of vertices. Observe that at most $k$ vertices in $S$ is a leaf, so at least $|S|-k$ vertices in $S$ has degree at least two. Thus, by double-counting the pair $$\{(v,e) : v\in S,\ e\in E(T),\ v\text{ is incident to } e\},$$we obtain that $$k + 2(|S|-k) \leq |E(T)| = n-1 \implies |S| \leq \frac{n+k-1}{2}.$$Thus, $\tfrac{n+k-1}{2}$ is indeed the maximum. Extracting the equality cases, we discover that All $k$ leaves must be in $S$. The rest $|S|-k$ vertices in $S$ must have the degree exactly two. There is no edge that connects two vertices within $T\setminus S$. This means that $S$ and $T\setminus S$ form a 2-coloring of the graph. Now, we are ready to conclude. Assume for the contradiction that the longest path has an odd length. Then, due to the coloring, one of the two ends must be in $T\setminus S$. This end cannot connect to any other vertices because otherwise, the path would not be the longest. Thus, this end must be a leaf, a contradiction to the first item in the list.

**** Let $n(T)$ denote the number of vertices of a tree $T$ and $k(T)$ denote the number of leaves of $T$. We claim that any set of at least $\lceil \frac{n(T)+k(T)-1}{2}\rceil + 1$ vertices of $T$ has some two vertices adjacent, which suffices. The proof is by induction on $|T|$. At $|T| = 0$ and $|T| = 1$, the result is clear because no such set exists. Now consider such a set $S$ of at least $\lceil \frac{n(T)+k(T)-1}{2}\rceil + 1$ vertices. Let $v$ be a vertex of $T$. Let $U$ be the set of vertices with maximal graph theoretic distance $N$ from $v$. Pick $u\in U$. If $u\not\in S$, the result follows because \[|S| \ge \left\lceil\frac{n(T)+k(T)-1}{2}\right\rceil+1\ge \left\lceil\frac{n(T)-1+k(T)-1}{2}\right\rceil+1 \ge \left\lceil\frac{n(T\setminus \{u\})+k(T\setminus \{u\})-1}{2}\right\rceil+1.\]If $u\in S$, let the neighbor $w$ of $u$ be connected to $s$ other vertices with $s\ge 1$. Let $Z$ be the set of vertices connected to $w$ in $U$ along with $w$, so $|Z| = s+1$. Note that $w$ is not in $S$ or we are done. Then \[|S| \ge \left\lceil\frac{n(T)+k(T)-1}{2}\right\rceil+1 = \left\lceil\frac{n(T) - s-1+k(T)-s+1-1}{2}\right\rceil+1 + s \ge \]\[\left\lceil\frac{n(T\setminus Z) + k(T\setminus Z)-1}{2}\right\rceil+1 + s.\]Note that the latter is at least $1$ more than the maximal number of elements in an independent set of $T\setminus Z$ along with every element of $Z\setminus \{w\}$, so we are done because $S$ must then not be an independent set. Claim: A longest path in $T$ is between two leaves. Solution: Suppose otherwise for some longest path. Let the path be between $u$ and $v$. WLOG $u$ has two neighbors, $w$ and $x$. Then the distance between $w$ and $v$ is $1$ less than the distance between $u$ and $v$. Then there is exactly one path from $v$ to $x$: $v\to w \to u \to x$ by the definition of a tree, which has distance $1$ more than the distance from $v$ to $u$, contradiction. $\fbox{}$ Claim: A tree $T$ such that there is a subset $S$ with $\lceil \frac{n(T)+k(T)-1}{2}\rceil$ vertices, no two of which are adjacent, has $n(T)+k(T)$ odd. Moreover, the tree is made by gluing together stars consisting of a vertex and its neighbors, of which there are at least two, with the structure before any stars are added being a single vertex. Solution: The proof is by induction on $|T|$. The result is clear at $|T| = 1$ and no tree with $|T| = 2$ has an independent subset with $2$ vertices. Root the tree about leaf $v$ and let $U$ be the set of vertices furthest from $v$, so each is a leaf. Let $u\in U$ be arbitrary. If $u\not\in S$, note \[\left\lceil \frac{n(T)+k(T)-1}{2}\right\rceil = |S| \le \left\lceil \frac{n(T\setminus \{u\})+k(T\setminus \{u\})-1}{2}\right\rceil \le \left\lceil \frac{n(T)+k(T)-1}{2}\right\rceil.\]Since equality holds, we get \[|S| = \frac{n(T\setminus \{u\})+k(T\setminus \{u\})-1}{2} < \frac{n(T)+k(T)-1}{2},\]absurd, by the induction hypothesis. Thus $u\in S$. Then let $u$ have sole neighbor $w$ with degree $s+1$. Since $w\not\in S$, all other leaves connected to $w$ must be in $S$, since the bound on $|S|$ is tight. Let the sole vertex connected to $w$ that is not a leaf be $x$. Let the set of the $s$ leaves connected to $w$ along with $w$ be $Z$. We claim $x$ has no neighbors further from $v$ than it besides $w$, which would mean $w$ is the center of a star that could be removed freely. Otherwise, we observe \[\left\lceil \frac{n(T)+k(T)-1}{2}\right\rceil = |S| \le \left\lceil \frac{n(T\setminus Z)+k(T\setminus Z)-1}{2}\right\rceil + s = \frac{n(T\setminus Z)+k(T\setminus Z)-1}{2} + s=\]\[\frac{n(T) - s-1+k(T)-s-1}{2} + s = \frac{n(T)+k(T)-2}{2}.\]Since $\frac{n(T)+k(T)-2}{2}$ is an integer, this is absurd. $\fbox{}$ Thus the tree is made of stars, meaning that the result readily follows from induction because $x$ must be a leaf before adding $Z$.

This is simple if you have solved https://codeforces.com/problemset/problem/1566/E before. A sketch: Consider the greedy algorithm for finding the maximum independent set of a tree. Root the tree at some vertex $r$. The algorithm repeatedly does the following until the tree has $<2$ nodes: pick the deepest leaf $l$. Let $v$ be its parent, and let $S$ be the set of children of $v$ (all of them are leaves). Add all elements of $S$ to the independent set and remove $S \cup v$ from the tree. Correctness of the algorithm is easy to prove. So at each step, the algorithm removes a star from the tree, and adds all its non-core elements to the independent set. It follows that the maximum independent set has size $n-t$ where $t$ is the number of stars removed. Now suppose we have found $S_1,S_2,...,S_t$: the stars removed by the algorithm. Given this information, we try to find the minimum number of leaves the original tree can have. Call the non-core elements of the stars (ie, those picked in the independent set) good, and the core elements bad. There are exactly $n-t$ good nodes. If a good node does not have any bad child, it is a leaf in the original tree. So to minimize the number of leaves, each bad node has to be made a child of a distinct good node. However, note that the topmost bad node, ie the core of the last star removed by the algorithm, cannot be the child of any good node. Using these facts, one easily sees that the maximum independent set has size $\leq (n+k-1)/2$, and for equality to hold, each bad node except the last one must be the child of a distinct good node and the last bad node must not be a leaf. This implies that the path between any two leaves must alternate between bad and good nodes. Since all leaves are good nodes, the result follows.

Does this work? I will only post an outline because I don't feel like writing out the details. 1) Call a subset of vertices of $T$ $\emph{good}$ if no two vertices in the set are adjacent. If $m$ is the maximum size of a good subset of the vertices of $T$, then there exists a good subset of the vertices of $T$ of size $m$ containing all the leaves of $T$ (other than the trivial exception of $n=2$). 2) Both endpoints of a maximal length path must be leaves. 3) We induct on $n$. Take a tree $T$ satisfying the hypothesis in the problem statement, remove all its leaves, and then remove all the leaves of the resulting tree to obtain a tree $T'$. Using (1), one can show that $T'$ also satisfies the hypothesis. Using (2), one can show that the longest path in $T$ has exactly $4$ more edges than the longest path in $T'$, and we are done. Any base cases where $T'$ has $1$ or no vertices can be handled easily.

Take the largest path and suppose it has an odd number of edges, i.e $2x$ for an integer $x$ vertices. The two ends of this path are leaves and we can take at most $x$ of the vertices on it for the maximal non-adjacent subset. Take a branch of the tree that starts from one of the vertices on the largest path, without this vertices. Greedily pair non-paired yet vertices up from this branch, except if they are a leaf or adjacent to a leaf, since we can assume that all leaves are part of the largest non-adjacent subset. This subset can contain at most $x$ vertices from the largest path, all remaining $k-2$ leaves, and half of the paired vertices, for a total of $$x+k-2+ \frac{n-2x-k+2}{2} = \frac{n+k-2}{2}$$which contradicts the problem statement. In fact, it didn't really matter that we chose the longest path, all paths between two leaves should have an even number of edges.

Let $P$, the longest path in $T$, have length $L$. suppose that we have a subset $S$ with at least $\tfrac{n+k-1}{2}$ vertices. Define a branch to be a maximal set of connected vertices with degree $2$ or $1$, and containing at least one leaf. Clearly a branch of $m$ vertices can have at most $\tfrac{m+1}{2}$ vertices belonging to $S$. Now, suppose that there exists some branch with $m$ vertices that is not a subset of $T$. Upon deleting this branch to form $T'$, the longest path in $T$ is still $P$, while removing $m$ vertices and one leaf (since the vertex connecting the branch to the rest of $T$ has degree $\geq 3$, so isn't a leaf after this). It is thus necessary for some subset $S'$ of $T'$ to contain at least $\tfrac{(n-m)+(k-1)-1}{2}$ vertices, otherwise there must be less than $$\frac{(n-m)+(k-1)-1}{2}+\frac{m+1}{2}=\frac{n+k-1}{2}$$non-adjacent vertices, contradiction. Repeat this process until we are left with only $P$, so we have $L$ vertices and $2$ leaves. Then it is trivial to check that there exists a subset of $\tfrac{L+1}{2}$ non-adjacent vertices of $P$ only if $L$ is odd, which means that $P$ must contain an even number of edges, as desired. $\blacksquare$ I spent a solid 5 minutes while solving this problem after getting to the end and forgetting that $P$ should have an even number of edges, not vertices, and wondering where I had messed up...

Let the subset be $S$ and let there be exactly $a\leq k$ leaves in $T$. Note that there are at least $\frac{n+k-1}{2}-a$ vertices in $S$ such that its degree is at least $2$. This mean that there are at least $2\cdot \left(\frac{n+k-1}{2}-a\right)=n+k-1-2a$ edges from all non-leaf vertices in $S$ to $S’$. The number of edges from leaves in $S$ to $S'$ is obviously $a\cdot 1=a$. Hence, after summing non-leaf and leaf, we have that there are at least $$(n+k-1-2a)+a=n+k-1-a\geq n-1$$edges from $S$ to $S'$ so equality holds since $T$ is a tree. Now, let consider what equality give us. The degree of every non-leaf vertex in $S$ is $2$. All $k$ leaves are in $S$. (because $a=k$) All edges in $T$ are from vertices in $S$ to $S'$. In other word, we get that $T$ is $T(S,S',E)$. (Bipartite) It's well-known that the longest path of a tree is the path that has two leaves as its start point and end point. But since all leaves are in $S$, and that $T$ is bipartite with $S,S'$ as its set, we get that the path length is even.

The key claim is the following: Claim: Let $S$ be said subset. Then, $\sum_{v\in S} \deg v=n-1$. Proof. First, for each vertex $v$ in $S$, highlight all edges coming out from $v$. Clearly $\sum_{v\in S} \deg v$ edges are highlighted, but no edge is highlighted twice which implies $\sum_{v\in S} \deg v \leq n-1$. However, we can say that \[\sum_{v\in S} \deg v \geq k\cdot 1+\left(\frac{n+k-1}{2}-k\right)\cdot 2=n-1\]by including $k$ leaves and all other vertices have degree $2$. This proves the claim. $\blacksquare$ Note that from the proof, equality must occur when only leaves and degree $2$ vertices are included. Also, not if we do the highlighting thing as describe earlier, every edge is highlighted once. This therefore means that if $V \not \in S$, then each edge going out from $V$ still must be highlighted. Thus all of $V$'s neighbors are in $S$. If $V\in S$, then no neighbor of $V$ is in $S$ trivially. Therefore, we can alternate coloring the vertices of $T$ between two colors, one being vertices in $S$ and one being vertices not in $S$. As the longest path in $T$ is between two leaves (trivial to prove: if not, just add on another edge from an endpoint) and all leaves are the same color, we conclude the result.

Call a vertex a leaf-parent if it is adjacent to a leaf. Lemma: We can always pick a maximal subset of nonadjacent vertices for which every leaf is chosen (and hence any leaf-parent is not chosen). Proof: If a leaf isn't chosen, unchoose its leaf-parent and choose the leaf instead. We now iterate the following process: For each leaf-parent, prune away all but one of its adjacent leaves. For each cut we make, the size of our maximal subset decreases by at most $1$ and $\tfrac{n+k-1}{2}$ decreases by $1$. (Thus, the inequality is preserved.) Furthermore, since every longest path begins and ends at a leaf, the length of the longest path is unaffected. Now, there must be some leaf-parent which has degree $2$. This is because if we were to delete all leaves from the graph, we'd still have a tree – the only vertices in this remaining tree which could be leaves would be the original leaf-parents with degree $2$. So, there exists some --A--B in our graph. Deleting these two vertices from the graph would decrease the maximal subset by exactly $1$ and decrease $\tfrac{n+k-1}{2}$ by at least $1$. (Thus, the inequality is preserved). Furthermore, if our original longest path didn't end at --A--B, nothing changed; on the other hand, if it did contain --A--B, the parity of the longest path wouldn't have changed. Each iteration of this process decreases the number of vertices in our graph by at least $2$, and leaves us with a graph that still satisfies the $\tfrac{n+k-1}{2}$ inequality. Thus, when we stop we have either $1$ or $2$ vertices. The latter case fails the $\tfrac{n+k-1}{2}$ inequality, so when we stop we have a tree with $1$ vertex. This graph obviously has a longest path of $0$, which is even, so all graphs satisfying this property have a longest path with even length.

Suppose this wasn't the case and consider a tree that doesn't satisfy the properties with the minimal possible number of vertices, say $n$. Call this tree $T$ and suppose it has $k$ leaves. Additionally, there exists a subset of $\frac{n + k - 1}{2}$ vertices of $T$ that aren't adjacent, but the longest path of $T$ contains an odd number of edges. Claim: All leaves must be in every longest path of $T$. Proof: Suppose otherwise for some leaf $L$. Let $P$ be a longest path of $T$ that doesn't contain $L$. Now consider tracing the graph from $L$ until you hit a vertex of degree at least $3$ (clearly there is only one way to do this) and let the branch, $B$, of $L$ be the set of all the vertices traced (aside from the one with degree $\ge 3$). If a vertex of $P$ was in $B$, then one direction of the path from this vertex must only contain vertices in $B$ (as there is only one way to go outside of $B$ in a path from this vertex), so by the maximality of the size of $P$, $L$ must be in $P$, absurd. Hence no vertex of $P$ is in $B$. Consider the graph $T'$ where all the vertices of $B$ are deleted. Note that $T'$ is still a tree and the number of leaves in $T'$ is $k - 1$ (as one leaf is deleted, but of the vertices that remain in $T'$, only a vertex with degree $\ge 3$ decreases in degree). Now let $r$ be the number of vertices in $B$. Clearly $T'$ now has $n - r$ vertices. Note that the maximal size set of vertices in $B$ of which no two are adjacent is $\frac{r + 1}{2}$ (by splitting $B$ into $\left \lfloor \frac r2 \right\rfloor $ groups of two adjacent vertices). Hence there must exist a subset of vertices in $T'$ that has at least $\frac{n + k - 1 - (r + 1) }{2} = \frac{(n - r) + (k - 1) - 1}{2}$ vertices, no two of which are adjacent. However, the longest path in $T$ still remains in $T'$, and we can't have any path of greater size than this in $T'$ (since $T'$ is a subgraph of $T$), so the longest path of $T'$ is odd. However, $T'$ has less than $n$ edges, contradiction to the minimality of $n$. $\square$ Fix some longest path of $T$. This path cannot contain more than two leaves, implying that $T$ has at most two leaves, so $T$ must be a path itself. Since $T$ has an odd number of edges, $n$ is even, so let $n = 2t$. Notice that if we split $T$ into $t$ groups of two adjacent vertices (which is clearly possible), at most one vertex in this group can be part of a no two adjacent subset, so the subset must contain at most $\frac{n}{2} < \frac{n + k - 1}{2}$ vertices, absurd. Hence the longest path of $T$ must contain an even number of edges.

Claim: At most $\tfrac{n+k-1}{2}$ vertices can be non-adjacent. Proof. Let $S$ be a set of non-adjacent vertices. Now, eliminate an edge $E$ if it consists of a vertex $v \in S$. An edge clearly cannot be eliminated twice as this contradicts the non-adjacent condition. At most $k$ vertices eliminate only $1$ edge, implying that at least $|S|-k$ vertices eliminate at least $2$ edges. Therefore we have the following bound: $$\underbrace{n-1}_{\# \text{edges}} \ge \# \text{eliminated edges} \ge 2(|S|-k) + k$$which clearly gives the result. $\blacksquare$ This clearly implies that equality must be achieved, so $|S| = \tfrac{n+k-1}{2}$. Now, we can freely assume the equality case in the above bound. Notice that all $k$ leaves must be in $S$, and all edges must have been eliminated. Therefore, no two vertices not in $S$ can be adjacent. Call vertices in $S$ to be good, and bad otherwise. Claim: The maximal path must start at a leaf and end at a leaf. Proof. Assume it ends at a vertex $v$ with degree at least $2$. Then we can simply move to the other adjacent vertex to $v$, contradiction. The argument for the starting vertex is clearly analogous. $\blacksquare$ Now, the longest path must start and end at leaves (which are both good), and alternate between good and bad vertices, implying that there are an even number of edges.