Show that a matched set of nodes forms a matroid

Question

Let $G=(V,E)$ denote a graph. We call a subset of nodes $V^\prime\subset V$ matched if there is a matching $M\subset E$ in $G$ such that $M$ contains all nodes in $V^\prime$. We define the family of sets $U=(V,\mathcal{I})$ with

$$\mathcal{I}:=\{I\subset V\;:\;I\textrm{ is matched regarding }G\}.$$

Show that $U$ is a matroid.

I have quite some problems to even understand what a matroid actually is, though I have quite a bunch of definitions here. Without getting a feeling on how to interpret such a structure I had the following ideas:

• Show that $U$ is a independence system with the definition $$B\in\mathcal{I},\;A\subset B\implies A\in\mathcal{I}.$$ The first trivial case would be the empty set of nodes which is always a subset of every set and therefore should be in every matching, too. The second case is still confusing -- i would like to show that we can choose an arbitrary matching $M\in\mathcal{I}$ but every subset of $M$ (even $\emptyset$) is obviously in $\mathcal{I}$ because the nodes were still matched.
• Show that $U$ is a matroid by using the term of the rank where $$r_+(U):=\max\{|\mathcal{B}|\;:\;\mathcal{B}\textrm{ is a base of }U\}\quad\text{ and }\quad r_-(U):=\min\{|\mathcal{B}|\;:\;\mathcal{B}\textrm{ is a base of }U\}$$ and I would have to proove $r_+(U)=r_-(U)$ but I can't do that due to the lack of my understanding what a base would be in this context.

I appreciate any help on how to solve this or even understand what this is about.

Answer 1

As I noted in a comment, the problem is very sloppily formulated. At least some of your confusion in the paragraph following the first bullet point appears to be related to this.

First it's $\mathcal I$ that's a family of sets, not $U$ (which is a pair of a set and a family of sets). Second, a subset $M$ of $E$ is a set of edges and thus cannot contain nodes. The intended meaning is that for all nodes $v\in V'$, $M$ contains an edge incident at $v$, i.e., that $M$ covers $V'$.

Your first attempt starts off in the right direction, but with $M\in\mathcal I$ you make a similar mistake as the problem author, since $\mathcal I$ is a family of sets of nodes, not of edges.

Here's a proof that $U$ is an independence system with the augmentation property.

First, the empty matching covers the empty set of nodes, so $\emptyset\in\mathcal I$.

Also, if $A'\subset A\in\mathcal I$, then $A'\in\mathcal I$, as the matching that is a witness for $A$ is also a witness for $A'$.

Finally, we need to show that if $A\in\mathcal I$ and $B\in\mathcal I$ with $|A|\gt|B|$, then there is $a\in A\setminus B$ such that $B\cup\{a\}\in\mathcal I$. This is the only graph-theoretically non-trivial part of the proof.

So let $A\in\mathcal I$ and $B\in\mathcal I$ with $|A|\gt|B|$, and let $M$ be a witness for $A$ and $N$ a witness for $B$. If there is an $a\in A\setminus B$ that is covered by $N$, we can add it to $B$ and are done. If there is an $a\in A\setminus B$ that is covered by an edge $e\in M$ whose other node isn't in $B$ either, then we can add $a$ to $B$ and $e$ to $N$ and are done. If there is an $a\in A\setminus B$ that is covered by an edge $e\in M$ whose other node is in $B$ and is covered by an edge $f\in N$ whose other node isn't in $B$, then we can add $a$ to $B$, remove $f$ from $N$ and add $e$ instead, and are done. The only case left is that all nodes in $A\setminus B$ are covered by an edge in $M$ whose other node is in $B$ and is covered by an edge whose other node is also in $B$. But in that case, since $A$ has more nodes than $B$, there must be at least one pair $b_1,b_2\in B$ matched by an edge $f\in N$ such that there are nodes $a_1,a_2\in A\setminus B$ and edges $e_1,e_2\in M$ with $e_1=(a_1,b_1)$ and $e_2=(a_2,b_2)$. Then we can add $a_1$ and/or $a_2$ to $B$, remove $f$ from $N$ and add $e_1$ and $e_2$ instead. Thus, in all cases, we can find a node $a\in A\setminus B$ and a matching witnessing $B\cup\{a\}$.

Answer 2

Matroids can be viewed as a generalization of the concepts 'linearly indepent', 'basis' for vectors in a vector space. Such a generalization usually goes as we pick out some important property of the concept to be generalized, and keep only them on an axiomatic level.

If a matroid $(V,\mathcal I)$ is given, then elements $I\in\mathcal I$ are subsets of $V$, called independent sets (that is, an $S\subseteq V$ is independent iff $S\in\mathcal I$, by naming). There are more, equivalent definitions for a matroid, see also Wikipedia. One is, as you started to write:

1. The empty set is independent (in axiomatic level, it is just $\emptyset\in\mathcal I$).
2. Any subset of an independent set is independent.
3. If one independent set, $A$ contains more elements than another one, $B$ then $B$ can be extended by at least one more element --moreover this element can be found in $A$-- such that it still remains independent (hence, by induction, can also be extended by $|A|-|B|$ number of elements).

This 3. is an important property of linear independence in vector spaces, and essentially this one implies that the dimension of a (finite dim.) vector space is uniquely determined, i.e. each basis have the same number of basisvectors.

Try to also prove this axiom 3. for the given set, and try to connect the other definition, using 'bases' (basis:=maximal independent set, i.e., $B\in\mathcal I$ is a basis, iff however we extend $B$ it is not independent any more, that is, iff for all $x\in V$, $B\cup\{x\}\in\mathcal I\implies x\in B$)..