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$

Question

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.

Answer 1

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

Answer 2

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.