Minimum Height Trees. Why does deleting leaves layer-by-layer give us the answer? Here is the problem I tried to solve. Finally, I gave up and found a solution which was correct. Here is it.

Here is the problem description:


  For a undirected graph with tree characteristics, we can choose any
  node as the root. The result graph is then a rooted tree. Among all
  possible rooted trees, those with minimum height are called minimum
  height trees (MHTs). Given such a graph, write a function to find all
  the MHTs and return a list of their root labels.
  
  The graph contains n nodes which are labeled from 0 to n - 1. You will
  be given the number n and a list of undirected edges (each edge is a
  pair of labels).
  
  You can assume that no duplicate edges will appear in edges. Since all
  edges are undirected, [0, 1] is the same as [1, 0] and thus will not
  appear together in edges.


Example 1 :

Input: n = 4, edges = [[1, 0], [1, 2], [1, 3]]

    0
    |
    1
   / \
  2   3 


Output: 1

Example 2 :

Input: n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]

 0  1  2
  \ | /
    3
    |
    4
    |
    5 


Output: 3, 4

Here is the solution I tried to understand:


  The basic idea is "keep deleting leaves layer-by-layer, until reach
  the root."
  
  Specifically, first find all the leaves, then remove them. After
  removing, some nodes will become new leaves. So we can continue remove
  them. Eventually, there is only 1 or 2 nodes left. If there is only
  one node left, it is the root. If there are 2 nodes, either of them
  could be a possible root.


I'm not sure I understand it so I could explain it to somebody. Why does deleting leaves layer-by-layer give us the answer?
Let $T$ be a tree, and let $T'$ be the tree formed from $T$ by removing all leaves (vertices of degree 1). Assume that $T$ contains at least three vertices, so that $T'$ is not empty. This implies that every leaf $f \in T$ has a (unique) neighbor $p(f) \in T$ which is not a leaf.

For $v \in T$, denote by $h_v(T)$ the height of $T$ when rooted at $v$.
I claim that the following hold:


  For every vertex $v \in T'$, $$ h_v(T) = h_v(T') + 1. $$
  For every leaf $f \in T \setminus T'$, $$ h_f(T) = h_{p(f)}(T) + 1. $$


For the first claim, consider $T$ rooted at a non-leaf $v$. The height of $T$ is the length of the maximal root-to-leaf path. Every such path gets shortened by one in $T'$, implying that $h_v(T) = h_v(T') + 1$.

For the second claim, let $x$ be a leaf farthest away from $p(f)$. We can assuming that $x \neq f$ since $p(f)$ has at least two neighbors, and $f$ is at minimal distance from $p(f)$. Clearly $d(f,x) = d(p(f),x) + 1$, and so $h_f(T) \geq h_{p(f)}(T) + 1$. The other direction follows from the triangle inequality, which implies that $d(f,y) \leq d(p(f),y) + 1$ for all nodes $y$.

The algorithm. If $T$ contains one or two vertices, then clearly all vertices are centers (roots of minimum height trees). Otherwise, by the second claim, no leaf can be a center, and so by the first claim, the centers of $T$ are the same as the centers of $T'$. This suggests the following algorithm for computing the centers of $T$:


  
  While $T$ contains at least three vertices, remove all leaves of $T$.
  Once $T$ contains one or two vertices, return all vertices of $T$.
  


The correctness of the algorithm follows the reasoning stated above.