Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
1  
@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
1  
No, the chain graph on $7$ vertices has just one centre. –  Brian M. Scott Feb 14 '13 at 6:05
show 3 more comments

2 Answers

up vote 2 down vote accepted
          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$.

share|improve this answer
    
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
add comment

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!

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.