Definition:Tree (Graph Theory)
From ProofWiki
Contents |
Definition
A tree is a simple connected graph with no circuits:
Equivalently, it can be defined as a simple connected graph with no cycles.
Node
The vertices of a tree are called its nodes.
Simple properties
- All trees are bipartite, from Bipartite Graph has 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.
Note
In some contexts, the term tree is used to mean rooted tree.
Sources
- Gary Chartrand: Introductory Graph Theory (1977): $\S 4.1$
