Editing Matroid (section)

=== Bases and circuits <span class="anchor" id="bases_circuits_anchor"></span> ===
{{Main|Basis of a matroid}}
A subset of the ground set <math> E </math> that is not independent is called ''dependent''. A maximal independent set – that is, an independent set that becomes dependent upon adding any element of <math>E</math> – is called a ''basis'' for the matroid. A ''circuit'' in a matroid <math> M </math> is a minimal dependent subset of <math>E</math> – that is, a dependent set whose proper subsets are all independent. The term arises because the circuits of [[graphic matroid]]s are cycles in the corresponding graphs.<ref name=w7-9/>

The dependent sets, the bases, or the circuits of a matroid characterize the matroid completely: a set is independent if and only if it is not dependent, if and only if it is a subset of a basis, and if and only if it does not contain a circuit. The collections of dependent sets, of bases, and of circuits each have simple properties that may be taken as axioms for a matroid. For instance, one may define a matroid <math> M </math> to be a pair <math> (E,\mathcal{B}) </math>, where <math> E </math> is a finite set as before and <math> \mathcal{B} </math> is a collection of subsets of <math> E</math>, called ''bases'', with the following properties:<ref name=w7-9/>

* (B1) <math> \mathcal{B} </math> is nonempty.

* (B2) If <math> A </math> and <math> B </math> are distinct members of <math> \mathcal{B} </math> and <math> a \in A \smallsetminus B</math>, then there exists an element <math> b \in B \smallsetminus A </math> such that <math> (A \smallsetminus \{ a \}) \cup \{b\} \in \mathcal{B}</math>.

This property (B2) is called the ''basis exchange property''. It follows from this property that no member of <math> \mathcal{B} </math> can be a proper subset of any other.