Difference between revisions of "Tree (graph theory)"

(Created page with "a tree is a branch with leaves")
 
 
(One intermediate revision by the same user not shown)
Line 1: Line 1:
a tree is a branch with leaves
+
A '''tree''' is an undirected [[Graph (graph theory)|graph]] which is both connected and acyclic. Equivalently, a tree is a graph <math>G=(V,E)</math> such that for any two vertices <math>u, v \in V</math> with <math>u \neq v</math>, there is exactly one path connecting <math>u</math> and <math>v</math> in <math>G</math>. Every tree on <math>|V|=n</math> vertices has exactly <math>n-1</math> edges.

Latest revision as of 16:51, 2 November 2020

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.