Deleting edge from tree gives 2 trees

Dependencies:

1. Tree
2. Bridge in graph
3. Deleting bridge from graph gives 2 components

Let $T = (V, E)$ be a tree. Suppose the edge $(u, v)$ is deleted from $T$ to get $T'$. Then $T'$ contains 2 connected components which are trees.

Proof

Since $T$ is a tree, there is a unique simple path between $u$ and $v$, which is $(u, v)$. Therefore, deleting $(u, v)$ will disconnect $u$ and $v$. This means $(u, v)$ is a bridge.

Since deleting a bridge gives 2 connected components, $T'$ contains 2 connected components.

Since $T$ is a tree, it is acyclic. Since removing an edge cannot create a cycle, $T'$ is also acyclic. Since each component in $T'$ is connected and acyclic, the connected components are trees.

Dependency for:

1. |E| = |V| - 1 in trees
2. Edge replacement in spanning forest using a cut

Info:

• Depth: 4
• Number of transitive dependencies: 8

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