Suppose G=(V,E) is a directed graph. Below are three different sets of subsets of edges. In each case either prove that the system M = (E,S) is a matroid (it has the inheritance property and meets one of the three equivalent conditions of Theorem 5.2.1) or give an example of a directed graph G and show that the system is not a matroid for G.

1. S is the subsets of edges I such that (V,I) has no directed cycles.

2. S is the subsets of edges I such that each vertex of (V,I) has outdegree at most 4.

3. S is the subsets of edges I such that each edge in (V,I) is in a cycle.

Theorem 5.2.1 Let M = (E, S) be an independence system. Then the fol- lowing conditions are equivalent:

(1) M is a matroid.

(2) For J,K ?S with |J|=|K|+1, there always exists some a?J \K such

that K ?{a} is also in S.

(3) For every subset A of E, all maximal independent subsets of A have the

same cardinality.