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