Every tree has either one or two center

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.