Tree has Center or Bicenter
 | This article needs to be linked to other articles. You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding these links. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{MissingLinks}} from the code. |
Theorem
Every tree has either:
- $(1): \quad$ Exactly one center
or:
- $(2): \quad$ Exactly one bicenter,
but never both.
That is, every tree is either central or bicentral.
Proof
A tree whose order is $1$ or $2$ is already trivially central or bicentral.
Let $T$ be a tree of order at least $3$.
First we establish that the construction of a center or bicenter actually works.
From Finite Tree has Leaf Nodes, there are always at least two nodes of degree $1$ to be removed.
By the Handshake Lemma, it is clear that $T$ must also have at least one node whose degree is greater than $1$:
- $\ds \sum_{i \mathop = 1}^n \map {\deg_G} {v_i} = 2 q$
where $q$ is the number of edges in $T$.
But from Finite Connected Simple Graph is Tree iff Size is One Less than Order:
- $q = n - 1$
So if each node has degree $1$, then $n = 2 \paren {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, from Connected Subgraph of Tree is Tree, after having removed those nodes, what is left is still a tree.
Therefore the construction is valid.
We need to show the following:
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 Complete 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 \ge 1$.
As there are always at least two nodes of degree $1$, $n + 1 - k \le 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.
The result follows by the Principle of Complete Induction.
$\blacksquare$