Why the set of all forests is a matroid?

Question

I am learning about matroids, and I can't understand why the set of forests forms a matroid.

To give the full context, the claim is the following:

If $G=G(V,E)$ is a graph and $I$ is defined as all subsets $X$ of $E$ s.t $X$ does not contain a cycle then $(E,I)$ is a matroid.

It is clear that a subset of a set without a cycle doesn't contain a cycle. The second part of the definition is not clear: Why,if $A,B\in I$ and $|A|>|B|$ there is $a\in A$ s.t $B\cup\{a\}\in I$.

I looked at the proof in Wikipedia (which is in the definition section) and I don't agree with it:

if $A$ and $B$ are both forests, and $A$ has more edges than $B$, then it has fewer connected components

My counterexample is this: Take a cycle graph, $C_{7}$ for example and take $A$ to have every second edge, then $|A|=4$ and $A$ has $3$ connected components. Take $B$ to be some $3$ edges connected to one another, then $|B|=3$ and $B$ has just one connected component. So $A$ has more edges, but fewer connected components than $B$.

I'd appreciate an explanation of how my example has a problem or a proof of the claim that $(E,I)$ is a matroid.

Answer 1

In your example, $G=K_7$, then $B$ has four connected components; one being a path of length $3$ with four vertices, and three more of one vertex each.

If you have two forests $A$ and $B$, and $|A|<|B|$, then $B$ will have fewer connected components than $A$, and so will have an edge $e$ joining two components of $A$. If this we not the case, each edge of $B$ would lie in a component of $A$, and so each component of $A$ would be a union of one or more components of $B$.

Adding the edge $e$ to $A$ gives a forest.

Answer 2

For future readers I think it may resolve some confusion (at least it did for me) to clarify what the "it" means in

if and are both forests, and has more edges than , then it has fewer connected components

"It" refers to the graph $(V, A)$ (I don't think sets of edges alone have a notion of "connected components"). To establish that fact, $(V, \{\})$ starts with $|V|$ connected components. Adding one edge $e$ means that $(V, \{e\})$ will have $|V|-1$ connected components since 2 of the (singeton) components get unified. When $A' \subset A$ and $(V,|A'|)$ has $|V| - |A'|$ connected components, we always find that adding another $a$ from $A \setminus A'$ unifies 2 components precisely because $A$ was assumed to be acyclic.