# Show that a matched set of nodes forms a matroid

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.

-
Perhaps a part of your confusion arises from the bad formulation of the problem -- it's $\mathcal I$ that's a family of sets, not $U$, and a subset $M$ of $E$ contains edges, not nodes. – joriki Nov 11 '12 at 12:22
@joriki: I don't think that this is exactly what makes it difficult for me. We never had any exmaples in class because our prof just shows us some definitions without even explaining how to work with such structures. In the end this concept of a matroid is still a mystery to me and I don't know whether my thoughts on what to do suffice and furthermore I don't know how to proove this while having such abstract definitions without any imagination how my sets might look like. – Christian Ivicevic Nov 11 '12 at 12:55

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\}$.

-
It will take some time to fully understand what you have written, i will come back in a few minutes if I have any questions - meanwhile you can have a look whether I made a mistake during the translation (you're from Berlin and probably know German ;) ) of the problem and confused everyone: i.imgur.com/sO8IU.png – Christian Ivicevic Nov 11 '12 at 15:04
@Christian: No, the translation seems fine; the sloppiness is already in the German original. – joriki Nov 11 '12 at 15:06
joriki: +1! You are so versatile! Did you think it out yourself, or you found some reference that guided your proof? I happened to dabble into this topic (matchings + matroid) very recently, and had the same and similar questions with the OP, such as math.stackexchange.com/q/234401/1281 – Tim Nov 11 '12 at 16:04
@Tim: I thought it out myself. The question you link to sounds interesting; I'll give it some thought. – joriki Nov 11 '12 at 16:24

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

-
I was now able to understand (1) and (2) but I have problems with the proof of (3). I was thinking about defining a basis $\mathcal{B}\in\mathcal{I}$ which contains all nodes of a perfect matching (which would be the entire set $V$), however this sounds incorrect because I think something would be missing here. Do you have any hint what I did misunderstand? – Christian Ivicevic Nov 11 '12 at 14:59