For matroids M = (S, U), the following property applies to U:
- If A, B ∈ U and |B| = |A| + 1 , then there must exist an x ∈ {B \ A} such that A∪ {x} ∈ U
I want to prove this property for the following two matroids
a)
S = set of edges of a connected graph G
U = all subsets of S that do not contain circles
My approach: If | B | = | A | +1, then there is at least one edge x in B, which can be added to A. A∪ {x} is a forest and A is a forest, but how do I know that A∪ {x} does not create a circle in A?
b)
S = set of vectors from $ \mathbb{R}^{n}$
U = all sets of linearly independent vectors from S
My approach: If there are |B| linearly independent vectors, and A contains |B|−1 vectors, then there must be a vector that is linearly independent of the vectors in A. Otherwise A would already be a basis of $ \mathbb{R}^{n}$, and B could not have more elements than A.
Would be glad for a scrutinizing look
Your approach to (b) is on the right track, but you need to show that there is a vector in $B$ that is linearly independent of the vectors in $A$; you can do this be showing that if $B\subseteq\operatorname{span}A$, then $B$ is not linearly independent.
For (a), suppose that $A$ and $B$ are the edge sets of forests $G_A$ and $G_B$, respectively, and that $|B|=|A|+1$. Let $V_A$ and $V_B$ be the vertex sets of $G_A$ and $G_B$, respectively. Suppose further that for each $e\in B$, $G_A+e$ contains a circuit. This can happen only if the vertices adjacent to $e$ are already in $V_A$, so $V_B\subseteq V_A$. Moreover, the vertices adjacent to $e$ must lie in the same component of $G_A$, so $G_A$ and $G_B$ have the same number $k$ of components.
Since $G_A$ and $G_B$ are forests, $|B|=|V_B|-k$ and $|A|=|V_A|-k$, and therefore
$$|V_B|-k=|V_A|-k+1\,.$$
But then
$$0\le|V_A|-|V_B|=-1\,,$$
which is absurd.