📂Graph Theory

Tree Graph

Definition ¹

A tree is a connected graph that does not contain any cycles.

Description

The concept of trees is commonly seen in areas such as data structures in computer science. For those in STEM fields who have even a cursory involvement with computers, they may have heard of heap sorting. The heap mentioned here is indeed a type of tree. The union of trees is intuitively called a Forest. In the case of a directed graph, a node with an input degree of $0$ is called the Root, and a node with an output degree of $0$ is called the Leaf. Trees may seem like a familiar and easily applicable concept, however, in pure mathematics, they reveal their complex true selves.

Theorem

The following are equivalent conditions for a graph to be a tree.

Let $T$ be a graph with $n$ vertices. The following statements are equivalent:

• (i): $T$ is a tree.
• (ii): $T$ does not have cycles and has $n-1$ edges.
• (iii): $T$ is a connected graph and has $n-1$ edges.
• (iv): Every edge in $T$ is a bridge.
• (v): There is only one path connecting any two vertices in $T$.
• (vi): $T$ does not have cycles but adding an edge would result in exactly one cycle forming.

---

• An edge $b \in G$ is called a bridge if its removal would disconnect the graph.

Proof

$(i) \implies (ii)$

Since $T$ does not contain any cycles, removing any edge results in two trees. Inductively repeating this process shows that each tree will have exactly one fewer edge than the number of vertices. Conversely, the tree $T$ must have $n-1$ edges.

---

$(ii) \implies (iii)$

Suppose $T$ is not connected. Each component of $T$ does not have cycles and has $1$ fewer edges than vertices. However, this contradicts the premise that there are $n-1$ edges, thus $T$ must be connected.

---

$(iii) \implies (iv)$

Edges of a disconnected graph: Let a simple graph $G$ have $n$ vertices. If $G$ has $k$ vertices, then the number of edges $m$ satisfies the following: $$n-k \le m \le (n-k)(n-k+1)/2$$

Removing any edge from $T$ leaves the number of vertices as $n$ and the number of edges as $n-2$, thus $n-k \le n-2$, indicating that the number of components increases with the removal of any edge, meaning all edges in $T$ are bridges.

---

$(iv) \implies (v)$

As $T$ is a connected graph, any pair of vertices belong to at least one path. If a pair of vertices belongs to two paths, this would form a cycle, contradicting the premise that all edges are bridges.

---

$(v) \implies (vi)$

If $T$ already included a cycle, then any two vertices on that cycle would belong to at least two paths, contradicting the premise. If an edge $e$ is added to $T$, the vertices connected by $e$ are already connected, thus forming a cycle. Therefore, adding an edge to $T$ results in exactly one cycle forming.

---

$(vi) \implies (i)$

If $T$ is not a connected graph, adding edges to connect each component would not produce a cycle. However, this contradicts the premise, so $T$ must be connected and, given it does not contain cycles, $T$ is a tree.

■