*A collection M of nonempty subsets of a set E is a matroid on E if (1) no member of M is a proper subset of another, and (2) for a and b two elements of E, given X and Y members of M such that a is in the intersection of X and Y and b in X – Y, there exists a member Z of M such that a is not in Z, b is in Z and Z is contained in the union of X with Y. *

*Let E be a fixed set and M be a matroid on E. The members of E are called the cells and the members of M the atoms of the matroid. A dendroid D of M is a minimal subset of E that has nonempty intersection with every atom of M. *

*Let G be a graph, denote the set of vertices by V(G) and the set of edges by E(G). A spanning tree of G is a subgraph of G which is a tree and whose vertex set includes all V(G). Trees are acyclyc connected graphs. A principal forest of G is a subgraph of G whose intersection with each component of G is a spanning tree of that component. In general G contains a number of cycles. Each cycle is completely described by its set of edges. Denote the collection of all cycles of G given as nonempty subsets of edges by P(G). This is called the polygon-matroid of G. *

*The following is a nice elementary result from the mid-sixties proved by Tutte in his *Lectures on Matroids *(see Theorem 2.21).*

**Theorem.** The dendroids of P(G) are the complements in E(G) of the edge sets of the principal forest of G.

### Like this:

Like Loading...