About a proof of a proposition about the spanning tree. I cannot understand.

58 Views Asked by At

I am watching this lecture about the minimum spanning tree now.

  1. Let $G = (V, E)$ be a (undirected) graph.
    Let $\mathcal{T} = \{T | T \subset E, (V, T) \text{ is a forest.} \}$.
    Let $M = (E, \mathcal{T})$.
    In this lecture, the professor proves that $M$ is a matroid.

  2. Let $G = (V, E)$ be a connected (undirected) graph.
    In this lecture, the professor proves that if $(V, T)$ is a spanning tree of $G$, then $T$ is a maximal element of $\mathcal{T}$.

  3. In this lecture, the professor proves that if $T$ is a maximal element of $\mathcal{T}$, then $(V, T)$ is a spanning tree of $G = (V, E)$.
    And the proof is the following:
    Suppose that $H \in \mathcal{T}$ which is a maximal set and which is not a spanning tree.
    By matroid theory, any maximal element of $\mathcal{T}$ has the same size.
    And by 2., any spanning tree is a maximal element of $\mathcal{T}$.
    So, $|H| = |V| - 1$.
    Then, the professor says that since $H$ is not a spanning tree, $H$ has at least two components.
    I cannot understand the rest of the professor's proof.

If $(V, H)$ is not connected, then $|H| = \sum_{i=1}^k (n_i-1) = \sum_{i=1}^k n_i-k < |V| - 1$, where $n_i$ is the size of $i$th component, and this is a contradiction. And I think the proof is done.

But the professor continues to prove the theorem.

Why?

I cannot understand the last part of the professor's argument.