Question

A tree is called central if its center is K₁ and bicentral if its center is K₂. Show that every tree is either central or bicentral without using the theorem that the center of every connected graph G lies in a single block.

Answer 1

tree of order 1 or 2 is already central or bicentral;

let order of tree be >=3;

there are always at least two nodes(leaf) of degree 1 to be removed .

it is clear that T must also have at least one node whose degree is greater than 1:

where q is the number of edges in T.

But q=n−1 as Size of Tree is One Less than Order.

So if each node has degree 1, then n=2(n−1) and so n=2.

Therefore if n>2 there must be at least one node in T of degree is greater than 1.
Next, after having removed those nodes, what is left is still a tree.

Therefore the construction is valid.
We need to show the following:

1. T has only one center or bicenter;
2. T has either a center or a bicenter.

• Suppose T has more than one center or bicenter.

It would follow that at least one of the iterations constructing the center or bicenter disconnects T into more than one component.

That could only happen if we were to remove an edge between two nodes of degree greater than 1.

Hence T has at most one center or bicenter.

• Now to show that T has at least one center or bicenter.

The proof works by the Principle of Strong Induction.

We know that a tree whose order is 1 or 2 is already trivially central or bicentral. This is our base case.
Suppose that all tree whose order is n have at most one center or bicenter. This is our induction hypothesis.

Take a tree T whose order is n+1 where n>2.

Let T have k nodes of degree 1.

We remove all these k nodes.

This leaves us with a tree with n+1−k nodes.

As we have seen that T has at least one node whose degree is greater than 1, n+1−k≥1.

As there are always at least two nodes of degree 1, n+1−k≤n−1.

So after the first iteration, we are left with a tree whose order is between 1 and n−1 inclusive.

By the induction hypothesis, this tree has either a center or bicenter.