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.