Showing that any tree has a separator vertex such that the size of the separated components is at most $\lfloor\frac{k}{n}V(G)\rfloor$ The task is to show that one can always find such a separator vertex in a tree $T$ such that the created components have a size of at most $\lfloor\frac{k}{n}V(G)\rfloor, \frac{k}{n} \in (0, 1)$ in terms of the vertices. As an example let us consider, say,  $\frac{k}{n} = \frac{2}{3}$. Edit: As @Mike Earnest pointed out, $\frac{k}{n}$ should be greater than $\frac{1}{2}$.
My current best idea for the proof is to use some sort of a search algorithm, that starts from a leaf node of the tree $T$ and investigates the number of paths of length $1,2,\dots,k$ from that root node of the search. The main idea is to record how many nodes have been encountered, and once that number is equal to $\lfloor\frac{2}{3}V(G)\rfloor$ the search is terminated. By problem with the proof is that I have no way of knowing that the separation vertex is really encountered from the chosen root vertex of the algorithms, once the number of found vertices is $= \lfloor\frac{2}{3}V(G)\rfloor$.
I have a hunch that there are some general graph properties that I don't know, which would turn this problem to an easy one.
 A: I think the easiest way to prove this is with a minimality argument.
Let $T = (V,E)$ be our tree, and for any vertex $u\in V$, define the function $C:V\rightarrow \mathbb{N}$ that gives you the max number of vertices in a connected component of $T-u$:
$$C(u) = \max\{|V(T')| : T' \text{ a connected component of  } T-u\}$$
For our proof, we will assume to the contrary that $C(u) > \lfloor\frac{2}{3}|V|\rfloor$ for every vertex $u\in V$. We now choose a vertex $v$ that minimises $C(v)$. In other words, $C(v) \leq C(u)$ for all $u\in V$.
Since $C(v)> \lfloor\frac{2}{3}|V|\rfloor$, there is a connected component $T_1$ of $T-v$ with more than $\lfloor\frac{2}{3}|V|\rfloor$ vertices. This component is connected to the vertex $v$ by an edge $vw$ for some vertex $w$ in $T_1$ (see the picture). The edge $vw$ is a cut-edge (as every edge in a tree is), and we denote by $T_2$ the component of $T-vw$ that contains $v$. Observe that $|V(T_2)| < \frac{1}{3}|V|$ since $|V(T_2)| > \lfloor\frac{2}{3}|V|\rfloor$.

But now we can find a contradiction! Since every component of $T-w$ is either $T_2$, or a proper subgraph of $T_1$, we must have that $C(w) < C(v)$, contradicting the minimality of $v$, and completing the proof.

As an aside, this is the same rough idea as is used in the famous Lipton and Tarjan separator theorem for planar graphs (although the argument they use is a lot more sophisticated).
A: The theorem is false when $|V(G)|=2$ as there is no separator vertex.  We assume that $|V(G)|>2$.  Then there is a vertex of degree $>1$, and we can assume that $V$ is rooted at such a vertex.
Let $M=<\left\lfloor\frac{2}{3}V(G)\right\rfloor$.  Consider the subtrees rooted at the children of the root.  If all have at most $M$ vertices, then the root is the required separator vertex.  If not, exactly one subtree $T$ has more than $M$ vertices.  Root $V$ at the root of $T$ and repeat. In this step, the largest subtree must have fewer vertices than in the first step, because it is either a proper subtree of $T$ or it has one more more vertex than $V\setminus T$.  Therefore, this process must stop.
I just waved my hands to prove that the size of the largest subtree decreases; you should give an actual proof.
