home blog search about
◐
table of contents

tree

2023-03-23

a connected acyclic graph is called a tree (hence a tree is a connected forest).

the following cases are equivalent:

  1. the graph is a tree,
  2. between every two vertices there is a single path,
  3. is connected and upon the removal of any of the edges we get a non-connected graph,
  4. is connected and ,
  5. is acyclic and .

the degree of a tree is a the highest degree that any of its nodes have.