Let $G$ be a finite undirected tree and let $l_e,r_e$ to be the number of vertices in the two sub-graphs of $G$, after spliting it by removing the edge $e$.
Let: $$q_e=|l_e-r_e|$$
We say that the edge $e_0$ is a "center edge" if $q_{e_0}=min_{e\in E}\left \{ q_e \right \}$
Prove or disprove:
- Any finite tree has maximum two center edges.
- In any finite tree, all the center edges meet in one vertex.
My attempt:
- Wrong - star graph is a counter example.
- I think it's true buy I couldn't find a way to prove it. I thought to prove it with adjacency matrix but with no success.
Hint: given any two disjoint edges, show that there is an edge 'between' them with a lower value of $q$.
Edit: More Concrete Hint: suppose we had two disjoint center edges. Let $x_L$, $x_C$, and $x_R$ denote the number of vertices to the 'left' of the two edges, 'between' the two edges, and to the 'right' of the two edges (you must make rigorous this notion). Let $e$ be and edge between the two center edges. Show that $q_e$ is smaller than the $q$-value of either center edge we started with. (Feel free to define more variables as necessary.)