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