Let $G$ be a Graph. Let $\mathcal{F}\subset\mathcal{P}(V(G))$ be a family of sets of nodes. For every set $X\in\mathcal{F}$ it is true, that there is a maximum matching $M$ which does not contain any node $x\in X$.
I want to show, that $(V(G),\mathcal{F})$ is a Matroid.
Definition of a Matroid:
Let $E$ be a set and $\mathcal{F}\subset\mathcal{P}(E)$. $(E,\mathcal{F})$ is a matroid if:
- $\emptyset\in\mathcal{F}$
- $X\subset Y\in\mathcal{F}\Rightarrow X\in\mathcal{F}$
- $X,Y\in\mathcal{F}$ and $|X|>|Y|$ $\Rightarrow$ $\exists x\in X\setminus Y$ with $Y\cup\{x\}\in\mathcal{F}$
Edit: After dealing a little with Matroids I came up with this proof.
Every Graph $G$ has a maximum matching. The empty set $\emptyset$ contains no nodes, which could be covered by a maximum matching. So the empty set $\emptyset$ must be in $\mathcal{F}$ by definition of $\mathcal{F}$ in the exercise.
Let $B\in\mathcal{F}$. By definition there must be a maximum matching, such that no node $x\in B$ is covered. That is true for every subset of $B$, too. Hence it is true for $A\subset B$.
Let $A,B\in\mathcal{F}$ and $|A|<|B|$. There are two cases:
- $A\setminus B=\emptyset$: Then $A\subset B$ and this case is solved with 2. (above)
- $A\setminus B\neq\emptyset$: By assumption it is true that $A,B\in\mathcal{F}$. By definition is a maximum matching $\mathcal{M}_A$ corresponding to the set $A$ and a maximum matching $\mathcal{M}_B$ corresponding to the set $B$. Let $x\in B\setminus A$:
- Let $x\not\in V(\mathcal{M}_A)$. Then $A\cup{x}\in\mathcal{F}$ is obviously true.
- Let $x\in V(\mathcal{M}_A)$. One must prove, that there is a maximum matching $\mathcal{M}_{A\cup {x}}$. $x\in B \Rightarrow x\not\in\mathcal{M}_B$. There is a $y\in V(G)$ such that $y\not\in\mathcal{M}_A$ and $y\in\mathcal{M}_B$ because every Base in $\mathcal{F}$ has the same cardinality. Because $y\not\in\mathcal{M}_A$ it is true that $y$ is in the Base $\mathcal{B}_A$ ($A\subset \mathcal{B}_A$). By construction $y$ and $x$ are not in $\mathcal{B}_A \cap \mathcal{B}_B$, and with the exchange lemma of Steinitz the proof is finished.
What do you think about this approach? My native language is German, so I tryed to translate my proof as well as I could. Mathematical and language corrections are both welcome! :-)