Properties of Tree

Quoting from Dasgupta, Papadimitrou, and Vazirani textbook:

“Trees A tree is an undirected graph that is connected and acyclic.”


Trees have these properties, quoting from DPV again:

  1. A tree on n nodes has n − 1 edges
  2. Any connected, undirected graph G = (V, E) with |E| = |V| − 1 is a tree.
  3. An undirected graph is a tree if and only if there is a unique path between any pair of nodes.

Leave a Reply

Your email address will not be published. Required fields are marked *