# Connected graph with minimum distance

How do i show this proof?

If $G$ is a connected graph then its center is the vertex $v$ such that the maximum of distances from $v$ to the other vertices of $G$ is minimal possible. Prove that a tree has either one center or two adjacent centers. Give an example of a tree of each type with $7$ vertices.

#### Solutions Collecting From Web of "Connected graph with minimum distance"

          a---b---c---d---e---f---g


The chain graph shown above has only one centre, $d$. The largest distance from $d$ to any other vertex is $3$, from $d$ to $a$ and from $d$ to $g$. The largest distance from $c$ to any other vertex is $4$, to vertex $g$, which is greater than $3$, so $c$ is not a centre. Similarly, the greatest distance from $e$ to any other vertex is $4$, to $a$, and you can check that the other vertices are even worse.

          a
\
\
b---c---d---e---f
/
/
g


The tree above has two centres; can you find them?

HINT for the proof: Let $T$ be a tree. If $u$ and $v$ are any vertices of $T$, there is a unique path from $u$ to $v$ in $T$. (You’ve probably proved this already; if not, you’ll want to do so now.) Call the length of this path the distance between $u$ and $v$ in $T$. Among all pairs of vertices of $T$ pick two, $u$ and $v$, with the largest possible distance between them. If that distance is even, there’s a vertex smack in the middle of that path; prove that it’s the unique centre of $T$. If the distance between $u$ and $v$ is odd, the path looks, for example, like this:

          a---b---c---d---e---f


Now there is no vertex right at the centre of the path, but there are two, $c$ and $d$, that are closest to the centre; prove that those two vertices are the centres of $T$.

Another approach would be by removing leafs. First prove the following lemma:

$$\text{every tree has at least two leafs}.$$

Then, show that if $T$ is a tree, then

• If $|T| \leq 2$ then its every vertex is a center.
• If $|T| > 2$ then if you remove all the leafs, the resulting tree $T’$ has exactly the same set of centers.

Good luck!