Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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! :-)

share|improve this question

1 Answer 1

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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.