A Graph is a tree if no subgraph is a cycle. Lemma A connected Graph with nodes is a tree if and only if has exactly edges.