This problem came up during a recent (and already finished) coding competition on Hackerrank, I was wondering if someone stumbled upon a proof.
[This question is my paraphrasing of the original]
Let $G$ be an arbitrary tree, let "center" vertices $c_1, c_2 \in V(G)$ be such that the maximum distance of any vertex $v$ of $G$ to the nearest "center" is minimized, i.e. $$dr = \max(\{\min(d(v, c_1), d(v, c_2)), v \in V(G)\})$$ is minimal. Calculate the value of $dr$.
It's basically an extension of the concept of a center and radius of a tree to two vertices. I figured that $c_1, c_2$ both lie on every longest path in $G$ and that I could calculate $dr$ by finding an arbitrary longest path, say $u-v$, then finding a vertex $z$ such that $min(d(u, z), d(v, z))$ is maximal and finally computing $dr = \lceil d(u, z) / 2 \rceil$ or $dr = \lceil d(v, z) / 2 \rceil$, depending on which vertex $z$ is closer to.
This approach seems to be correct but I'm having a bit of trouble with the proof. It's obviously true if $G$ is a path graph since $c_1, c_2$ can be placed around the $1/4$ and $3/4$ marks. Subsequently adding more branches to $G$ so that it's always a longest path in the resulting tree never moves the "centers" away from $G$. They only move closer towards the middle of it if a long branch is added between the "centers" whose end vertex is farther away from the nearest "center" than the corresponding end vertex of $G$.
Can I find a proof of this somewhere? Can this be extended to an arbitrary number of "centers"? I'm not good with this sort of induction proofs on graphs.
Edit: Both points don't have to lie on every longest path after all. Example.
Yes, as far as i can observe your observation holds (any such centers are always on any longest path) and a weaker version seems to hold on any number of centers (we will see why later).
edit: this seems to be true only for trees $G$ with $r_2(G) < rad(G)$ and when restricting the choice of centers to those pairs among those fulfilling the initial requirements minimizing $d(e_1,e_2)$. I adjusted the proof for this.
Let me try to prove it here for 2 points:
Let $G$ be a tree and $e_1, e_2$ vertices that minimize $max_{v \in G}h(v) \\h(v):=min(d(v, e_1),d(v, e_2))$ with minimal distance $d(e_1, e_2)$
Let $n = max_{v \in G}h(v)$
We split $G$ into two trees $G_1$ and $G_2$ by $ v \in G_1 :\Leftrightarrow d(v,e_1) \leq d(v,e_2) , G_2 = G\backslash G_1$
This is achieved by removing a single edge $e$ from the unique path from $e_1$ to $e_2$ (why?)
We root $G_i$ in $e_i$ and split it into the branches pointing toward $e$ or away from it. We may assume the height of the branch pointing away from $e$ is at least $n-1$ in each $G_i$. Let us call the length of that branch at $e_i$ $L(e_i)$.
Else let us assume $L(e_1)<n-1$. We can now move $e_1$ one edge towards $e$ and have center points with smaller distance, a contradiction. We can move $e_1$ because $e$ is not adjacent to $e_1$, otherwise $e_2$ would be adjacent to $e_1$ and $B^n_{e_2} = G$, contrary to our assumption of $n=r_2(G)<rad(G)$
Now we get paths of length $L(e_1)+d(e_1, e_2)+L(e_2) \geq 2n+d(e_1,e_2)-2$ passing through both $e_1$ and $e_2$. It is for us to show any path not passing both is shorter.
Any path crossing neither $e_i$ can be at most $2(n-1)$ long because $G$ is a tree and $d(v, e_i) \leq n$ for at least one $i=1,2$.
A path crossing one of $e_1, e_2$ can be at most $L(e_i)+(d(e_1, e_2)-1)+(n-1)$ long if it passes $e_i$ (why?). We now have $L(e_i)+d(e_1, e_2)+n-2 < L(e_1)+d(e_1, e_2) + L(e_2)$ because of $L(e_{1,2})\geq n-1$ which completes our proof.
For an arbitrary number k of points it is also possible to split $G$ like this, and it seems (because we can arrange the $G_i$ on a tree themselves (neighboring iff neighbouring) that any longest will always go through at least 2 $e_i$ (an easy example why it can't alwas go through all is this for k=4 or this for k=3 (note how here after putting down 2 centers the third can be put anywhere and depending on choice longest paths may or may not always cross all)
edit: We surely have to also restrict trees for this more general case. Without further thought a restriction to trees with $r_i < r_{i-1}$ (for $i=k$ or even $i \leq k$) or similar would seem intuitive.