Question

Let G = (X, E) be a connected graph. The distance between two vertices x and y of G is the shortest length of the paths linking x and y. This distance is denoted by d(x, y). We call the center of the graph any vertex x such that the quantity max y∈X d(x, y) is the smallest possible. Show that if G is a tree then G has either one center or two centers which are then neighbors

Answer 1

  let G be a tree having more than two vertices,then G has two or more pendant vertices. Delete all the pendant vertices from G, the resulting graph G' is again a tree. The removal of all pendant vertices from G uniformly reduces the eccentricities of the remaining vertices (vertices in G') by one. Therefore the centers of G are also the centers of G'. From G' remove all pendant vertices and get another tree G''.  Continuing this process, we either get a vertex, which is a center of G, or an edge whose end vertices are the two centers of G.