# 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.

-
Can you do any part of this? E.g., can you find a tree with $7$ vertices, and decide which type it is? –  Gerry Myerson Feb 14 '13 at 5:41
One example of tree graph with 7 vertices is a straight line with 7 connected vertices, how do i know what type it is? –  Jane Ke Feb 14 '13 at 5:53
@JaneKe Look at the definition of a center of a graph. Does your graph have $1$ center or more than one? –  Andrew Salmon Feb 14 '13 at 5:56
@AndrewSalmon it has more than 1 center, got it now. –  Jane Ke Feb 14 '13 at 6:04
No, the chain graph on $7$ vertices has just one centre. –  Brian M. Scott Feb 14 '13 at 6:05

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$.

-
The two centers are b and d? –  Jane Ke Feb 14 '13 at 6:13
@Jane: The maximum distance from $b$ to another vertex is $4$, to $f$; the maximum distance from $d$ to another vertex, however, is only $3$, to $a$ or $g$. Thus, only one of them can possibly be a centre; which one? And when you’ve answered that, what vertex is the other centre? –  Brian M. Scott Feb 14 '13 at 6:15
Ok got it thanks for clearing this up. The two centers are c and d –  Jane Ke Feb 14 '13 at 6:20
@Jane: There you go. –  Brian M. Scott Feb 14 '13 at 6:21

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!

-