Definition:Tree (Graph Theory)
This page is about Tree in the context of Graph Theory. For other uses, see Tree.
Definition
Definition 1
A tree is a simple connected graph with no circuits.
Definition 2
A tree is a simple connected graph with no cycles.
Node
The vertices of a tree are called its nodes.
Leaf Node
Let $v$ be a node of a tree $T$.
Then $v$ is a leaf node of a $T$ if and only if $v$ is of degree $1$.
If $T$ is a rooted tree, this is equivalent to saying that $v$ has no child nodes.
Finite or Infinite
Finite Tree
A tree is finite if and only if it contains a finite number of nodes.
Infinite Tree
A tree is infinite if and only if it contains a (countably) infinite number of nodes.
Also defined as
In some contexts, the term tree is used to mean rooted tree.
Also known as
Some sources refer to a tree as a free tree or an unrooted tree to distinguish it specifically from a rooted tree.
Examples
Arbitrary Example 1
Also see
- Results about trees can be found here.
 | This page or section has statements made on it that ought to be extracted and proved in a Theorem page. In particular: Separate pages for these results You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by creating any appropriate Theorem pages that may be needed. To discuss this page in more detail, feel free to use the talk page. |
- All trees are bipartite, from Graph is Bipartite iff No Odd Cycles (as a tree has no cycles at all).
- No (non-edgeless) tree is Eulerian, as it has no circuits, let alone Eulerian ones.