Lagmental Vicfred

Five Characterizations of a Tree Collapse to One Object by Vicfred

tags: mathematics, trees, graph distance, structural graph theory

Connectedness with n minus one edges, acyclicity with n minus one edges, and unique paths are equivalent. This is a compact note, but the quantifiers and hypotheses stay on the page.

Statement

A finite graph \(T=(V,E)\) is a tree when it is connected and acyclic. The unique simple path \(P_{uv}\) between two vertices makes distance and recursive decomposition especially rigid.

$$ |V|=n $$

A reliable calculation names domain and codomain. The notation \(\mathsf{data}\mapsto\mathsf{claim}\) is harmless only after both \(\operatorname{dom}\) and \(\operatorname{cod}\) have been fixed.

$$ T\ \text{tree}\Longleftrightarrow T\ \text{connected and }|E|=n-1 $$

Worked algebra

Here is a concrete symbolic test. Reading it from left to right reveals which transformation is reversible and which is only an implication.

$$ \begin{array}{c}\text{connected}+(n-1)\text{ edges}\\\Updownarrow\\\text{acyclic}+(n-1)\text{ edges}\\\Updownarrow\\\text{one simple }u\text{--}v\text{ path for every }u,v\end{array} $$

Conceptual compression

A good test for understanding is to change the presentation while keeping the invariant fixed. The aligned form makes that comparison unusually easy.

$$ \begin{aligned} \mathsf{D}\;&:\quad |V|=n,\\[5pt] \mathsf{C}\;&:\quad T\ \text{tree}\Longleftrightarrow T\ \text{connected and }|E|=n-1. \end{aligned} $$

Caveat

A rooted tree adds a parent relation that an unrooted tree does not possess. Statements about ancestors depend on the chosen root.

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] T\ \text{tree}\Longleftrightarrow T\ \text{connected and }|E|=n-1 \end{gathered}} $$

The important habit is to remember what was fixed before the calculation began and what was proved only afterward. The final display preserves that order.

This article was posted on Wed 08 February 2023. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.