Hello Readers

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.

Radius(T)=min{E(v); v∈v(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.

### Like this:

Like Loading...

*Related*

It’s clear mam

Thnku

LikeLike

Welcome

LikeLiked by 1 person

NICE EXPLANATION

LikeLike

thank you

LikeLike

Thanks mam

LikeLike

Explain with figure please.

LikeLike

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

LikeLike

tnx

LikeLike

Thank you

Please provide the Theorem on centroid also i.e

Every tree has a centroid consisting of one or two adjacent points.

LikeLike

Thank you..I will provide very soon

LikeLike

Well explained 😊

LikeLike

Thank you mam

LikeLike