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”

It’s clear mam
Thnku

Like

2. abhishek misra says:

NICE EXPLANATION

Like

3. Divya C says:

Like

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

5. Hari Priya says:

Well explained 😊

Like