G = (V, E) is a tree iff G is connected and |E| = |V|-1

Dependencies:

1. |E| = |V| - 1 in trees
2. In a connected graph (V, E), |E| ≥ |V| - 1
3. Tree iff connected and deleting edge disconnects

An undirected graph $G = (V, E)$ is a tree iff $G$ is connected and $|E| = |V|-1$.

Proof

If $G$ is a tree, it is connected and $|E| = |V|-1$.

Since in any connected graph $|E| \ge |V|-1$, it is not possible to delete an edge from $G$ without disconnecting it. Any connected graph from which deleting any edge disconnects the graph is a tree. Therefore, $G$ is a tree.

Dependency for: None

Info:

• Depth: 6
• Number of transitive dependencies: 12

Transitive dependencies:

1. /sets-and-relations/equivalence-classes
2. /sets-and-relations/relation-composition-is-associative
3. /sets-and-relations/equivalence-relation
4. Graph
5. Path in Graph
6. Tree
7. Tree iff connected and deleting edge disconnects
8. In a connected graph (V, E), |E| ≥ |V| - 1
9. Bridge in graph
10. Deleting bridge from graph gives 2 components
11. Deleting edge from tree gives 2 trees
12. |E| = |V| - 1 in trees