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

Dependencies:

  1. Tree
  2. Path in Graph
  3. |E| = |V| - 1 in trees

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

Proof

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

Suppose $G$ is acyclic and $|E| = |V|-1$. Let $G_1, G_2, \ldots, G_k$ be the connected components of $G$ and let $G_i = (V_i, E_i)$.

Each component is connected and acyclic, which makes it a tree. \[ |E| = \sum_{i=1}^k |E_i| = \sum_{i=1}^k \left(|V_i| - 1\right) = |V| - k \]

Therefore, $k = 1 \implies G = G_1 \implies G$ is a tree.

Dependency for: None

Info:

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. Bridge in graph
  8. Deleting bridge from graph gives 2 components
  9. Deleting edge from tree gives 2 trees
  10. |E| = |V| - 1 in trees