Difference between revisions of "Tree (graph theory)"

A tree is an undirected graph which is both connected and acyclic. Equivalently, a tree is a graph $G=(V,E)$ such that for any two vertices $u, v \in V$ with $u \neq v$, there is exactly one path connecting $u$ and $v$ in $G$. Every tree on $|V|=n$ vertices has exactly $n-1$ edges.