Properties of Tree

Quoting from Dasgupta, Papadimitrou, and Vazirani textbook:

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

p.135

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.