Determine whether M = ([3],B), with B = ([3] C 2), is a graphic matroid.

Question

I currently am learning about matroids in my discrete mathematics class. While I had problems understanding them at all at first, I think I am starting to see how they work. But now I have found a point which confuses me. I have the following assignment:

M = ([3],B) and B = ([3] C 2). Determine whether this is a graphic matroid and, if it is, determine it's graph.

Now, our previous matroids were all already given as graphs and there I found it easy to understand them. But here I've got some problems. I think that I know the following about matroids: A matroid is given through a set of the edges of a graph (Here where [3] is used) and the set of all the subsets of this first set which do not contain any cycles. In addition, a matroid must follow a certain set of rules:

The empty set must be part of the given set of subsets.

If A is part of the given set of subsets and B is a subset of A, then B is also a part of the given set of subsets.

If |A| = |B|+1, then there is an edge e in A/B, so that B + e is part of the set of subsets.

With these rules, I still am not sure how to tackle this question. What confuses me most is the fact, that the set of edges (if that is what it is supposed to be) is given through the set [3], which I interpret as the set {1,2,3}. And the set of subsets given here would be {{1,2},{1,3}{2,3}}. I am not sure how to interpret this exactly. Is this already not a matroid because the given set of subsets does not contain the empty set? And even if it did, would it be a matroid then, if it isn't already? And if it is or would be then, how would you find the graph that fits this matroid?

Thank you for reading!

Answer 1

The matroid you describe is given in terms of its bases $B$, while the axioms you cite are for the independent sets $I$. The bases are the maximal independent sets (by containment), while the independent sets are all the subsets of the bases.

In this particular case, the independent sets are

$$I = \{\emptyset,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\}\}.$$

For a graph $G$ and its corresponding graphic matroid, $B$ contains all spanning trees of $G$, and $I$ all forests of $G$. So, you need to find a graph with 3 edges ($[3]$) whose spanning trees are exactly the ones in $B$.