# Show that the complements of maximum matchings (extended down) form a matroid

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:

1. $\emptyset\in\mathcal{F}$
2. $X\subset Y\in\mathcal{F}\Rightarrow X\in\mathcal{F}$
3. $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.

1. 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.

2. 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$.

3. Let $A,B\in\mathcal{F}$ and $|A|<|B|$. There are two cases:

1. $A\setminus B=\emptyset$: Then $A\subset B$ and this case is solved with 2. (above)
2. $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$:
1. Let $x\not\in V(\mathcal{M}_A)$. Then $A\cup{x}\in\mathcal{F}$ is obviously true.
2. 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! :-)

-

Two remarks.

First, you haven't defined the matroid correctly. It contains all the sets of vertices satisfying your property of being disjoint from some maximum matching. Otherwise it's not a matroid - it needn't even contain the empty set.

Second, your proof of Claim 3 cannot possible be true since it doesn't use the condition that $|X| > |Y|$. Indeed, in matroids all the maximal sets ("bases") have equal cardinality. Take two different maximal sets $X,Y$. It's then impossible to add any element $x \in X \setminus Y$ to $Y$, since $Y$ is maximal.

In particular, your comment in Case 2, "It seems to me, that Claim 3 is true for every node $x \in X$" is completely unjustified. Your treatment of Case 3 is even more shaky - "The way I see it".

What's missing here is a proof of the only non-trivial part of the assertion that we have a matroid here - namely the extension property (your "Claim 3") in the case that $Y$ is not a subset of $X$ (otherwise it's not interesting, as you show).

This proof must use somehow the particular definition of your set system. For example, your proof never refers to matchings, let alone to maximal matchings.

-

Definition:
Let G be a agraph and $M_{A},M_{B}$ matchings. Define $G^* = G(V,M_{A} \Delta M_{B})$

1. an alternating path in $G^*$ is a path in which the edges belong alternatively to the matching $M_{A}$ and to the matching $M_{B}$.
2. an augmenting path in $G^*$ is an alternating path that starts from and ends on vertices matched by the same matching.
• Let $A,B\in\mathcal{F}$ and $|A|+1=|B|$. If there is an $e \in B\setminus A$ so that $A+e \in \mathcal{F}$ we are done. Assume there is no such e.
• Then look at $M_{A} \Delta M_{B}$ where $M_{X}$ is a maximum matching that does not contain any elment of X. Since $M_{A}$ and $M_{B}$ are maximum matchings $M_{A} \Delta M_{B}$ does not contain any augmenting path(If it would contain such path either $M_{A}$ or $M_{A}$ is not a maximum matching). Since for no $e \in B\setminus A$, $A+e$ is in $\mathcal{F}$ the symmetrical difference $M_{A} \Delta M_{B}$ contains alternating path (All $e \in B\setminus A$ are covered by $M_{A}$ but not by $M_{B}$). At least one path ends in an node x which is NOT in A. This is because otherwise for all path starting from $e \in B\setminus A$ there exists an $x \in A\setminus B$ in which the path ends. Then it follows $|A|=|A\cap B| + |B\setminus A|= |B| > |A|$. Thats a contradiction so there is at least on alternating path P with a starting point $e \in B\setminus A$ and an ending point x $\notin A$.
• Now remove all edges along P in $M_{A}$ and add all adges from $M_{B}$ along P to $M_{A}$ and call this created Matching $M_{A + e}$.
• $M_{A + e}$ is a maximum matching since we removed the same amount of edges that we added
• By construction $M_{A + e}$ does not cover any element of A and does not cover e which is element of $B\setminus A$
• it follows that $A+e$ is in $\mathcal{F}$
-