# Every tree has either one or two center

Today’s post is based on Tree which is an important topic in Graph theory.

Let’s have a look on some basic definitions and then we will be proving that every tree has either one or two centers.

Tree: A connected graph without any cycle is called a tree. i.e. no self loops, parallel edges and components are allowed in trees.

Pendant Vertex: A vertex with degree one in a tree is called a pendant vertex.

Note: A tree with n vertices (n>=2) has at least two pendant vertices.

Distance d(u,v): Distance between any two vertices in a tree is the number of edges in the shortest path between u and v.

Eccentricity E(v): Eccentricity of any particular vertex v in a tree is the maximum distance from vertex v to any other vertex w.

E(v)=max{d(v,w); w∈v(T)}, v(T) is vertices set of tree T.

Radius of Tree: Radius of tree is the minimum eccentricity among vertices of tree T.

Diameter of Tree: Diameter of tree T is the maximum eccentricity among the vertices of tree T.

Diameter(T)=max{E(v); v∈v(T)}

Center of Tree: A vertex with minimum eccentricity in a tree T is called center of tree T. in other words, set of all vertices whose eccentricity is equal to radius of graph is called center of tree T.

Theorem: Prove that every tree T has either one or two centers.

Proof: We will use one observation that the maximum distance max d(v,w) from a given vertex v to any other vertex w occurs only when w is pendant vertex.

Now, let T is a tree with n vertices (n>=2)

⇒T must have atleast two pendant vertices.

delete all pendant vertices from T, then resulting graph T’ is still a tree.

⇒ eccentricity E(v) in T’ is just one less than E(v) in T ∀ v in T’

again delete pendant vertices from T’ so that resulting T” is still a tree with same centers.

Note that all vertices that T had as centers will still remain centers in T’–>T”–>T”’–>..

continue this process untill remaining tree has either one vertex or one edge.

So at the end, if one vertex is there this implies tree T has one center.

If one edge is there then tree T has two centers.

end of proof.

Result: If a tree has two centers then these two centers must be adjacent.

Thank You.

## 12 thoughts on “Every tree has either one or two center”

1. Saud Ahmad says:

It’s clear mam
Thnku

Like

• Namita Tiwari says:

Welcome

Liked by 1 person

2. abhishek misra says:

NICE EXPLANATION

Like

• Namita Tiwari says:

thank you

Like

3. Anup verma says:

Thanks mam

Like

4. Divya C says:

Like

• Namita Tiwari says:

thanks for reading mam, I’ll update it soon.

Like

5. Anonymous says:

tnx

Like

6. Anonymous says:

Thank you
Please provide the Theorem on centroid also i.e
Every tree has a centroid consisting of one or two adjacent points.

Like

• Namita Tiwari says:

Thank you..I will provide very soon

Like

7. Hari Priya says:

Well explained 😊

Like

• Namita Tiwari says:

Thank you mam

Like