# Tree has Center or Bicenter

## 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.0

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 $q = n-1$ from Size of Tree is One Less than Order.

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:

$(1): \quad T$ has only one center or bicenter
$(2): \quad$T$has either a [[Definition:Center of Tree|center]] or a [[Definition:Bicenter of Tree|bicenter]]. Suppose$T$has more than one [[Definition:Center of Tree|center]] or [[Definition:Bicenter of Tree|bicenter]]. It would follow that at least one of the iterations constructing the [[Definition:Center of Tree|center]] or [[Definition:Bicenter of Tree|bicenter]] disconnects$T$into more than one [[Definition:Component (Graph Theory)|component]]. That could only happen if we were to remove an [[Definition:Edge (Graph Theory)|edge]] between two [[Definition:Node (Graph Theory)|nodes]] of [[Definition:Degree (Vertex)|degree]] greater than$1$. Hence$T$has at most one [[Definition:Center of Tree|center]] or [[Definition:Bicenter of Tree|bicenter]]. Now to show that$T$has at least one [[Definition:Center of Tree|center]] or [[Definition:Bicenter of Tree|bicenter]]. The proof works by the [[Principle of Complete Induction]]. We know that a [[Definition:Tree (Graph Theory)|tree]] whose [[Definition:Order of Graph|order]] is$1$or$2$is already trivially [[Definition:Central Tree|central]] or [[Definition:Bicentral Tree|bicentral]]. This is our base case. Suppose that all [[Definition:Tree (Graph Theory)|tree]] whose [[Definition:Order of Graph|order]] is$n$have at most one [[Definition:Center of Tree|center]] or [[Definition:Bicenter of Tree|bicenter]]. This is our induction hypothesis. Take a [[Definition:Tree (Graph Theory)|tree]]$T$whose [[Definition:Order of Graph|order]] is$n+1$where$n > 2$. Let$T$have$k$[[Definition:Node of Graph|nodes]] of [[Definition:Degree of Vertex|degree$1$]]. We remove all these$k$[[Definition:Node of Graph|nodes]]. This leaves us with a tree with$n + 1 - k$[[Definition:Node of Graph|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 [[Definition:Node of Graph|nodes]] of [[Definition:Degree of Vertex|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 [[Definition:Center of Tree|center]] or [[Definition:Bicenter of Tree|bicenter]]. The result follows by the [[Principle of Complete Induction]].$\blacksquare\$