Free matroid

The graphic matroid of a forest with 4 edges, which is the free matroid with a ground set of size 4 (also the uniform matroid U44). More generally, the graphic matroid of a forest with n edges is Unn.

In mathematics, the free matroid over a given ground-set E is the matroid in which the independent sets are all subsets of E. It is a special case of a uniform matroid; specifically, when E has cardinality n, it is the uniform matroid Unn. The unique basis of this matroid is the ground-set itself, E. Among matroids on E, the free matroid on E has the most independent sets, the highest rank, and the fewest circuits.

Every free matroid with a ground set of size n is the graphic matroid of an n-edge forest.

Free extension of a matroid

The free extension of a matroid M by some element e∉M, denoted M+e, is a matroid whose elements are the elements of M plus the new element e, and: