A graph $G$ is called acyclic if it has no cycles, a tree is an acyclic connected graph

  • every two vertices of a tree $T$ are connected by a unique path
  • every nontrivial tree has at least two end-vertices
  • if $T$ is a tree of order $n$ then the size of the tree is $m = n - 1$
  • additional definitions