Editing Graphic matroid (section)

==Definition==
A [[matroid]] may be defined as a family of finite sets (called the "independent sets" of the matroid) that is closed under subsets and that satisfies the "exchange property": if sets <math>A</math> and <math>B</math> are both independent, and <math>A</math> is larger than <math>B</math>, then there is an element <math>x\in A\setminus B</math> such that <math>B\cup\{x\}</math> remains independent.  If <math>G</math> is an undirected graph, and <math>F</math> is the family of sets of edges that form forests in <math>G</math>, then <math>F</math> is clearly closed under subsets (removing edges from a forest leaves another forest). It also satisfies the exchange property: if <math>A</math> and <math>B</math> are both forests, and <math>A</math> has more edges than <math>B</math>, then it has fewer connected components, so by the [[pigeonhole principle]] there is a component <math>C</math> of <math>A</math> that contains vertices from two or more components of <math>B</math>. Along any path in <math>C</math> from a vertex in one component of <math>B</math> to a vertex of another component, there must be an edge with endpoints in two components, and this edge may be added to <math>B</math> to produce a forest with more edges. Thus, <math>F</math> forms the independent sets of a matroid, called the graphic matroid of <math>G</math> or <math>M(G)</math>. More generally, a matroid is called graphic whenever it is [[isomorphic]] to the graphic matroid of a graph, regardless of whether its elements are themselves edges in a graph.<ref name="tutte65"/>

The bases of a graphic matroid <math>M(G)</math> are the full [[spanning tree|spanning forests]] of <math>G</math>, and the circuits of <math>M(G)</math> are the [[cycle (graph theory)|simple cycles]] of <math>G</math>. The [[Matroid rank|rank]] in <math>M(G)</math> of a set <math>X</math> of edges of a graph <math>G</math> is <math>r(X)=n-c</math> where <math>n</math> is the number of vertices in the [[Glossary of graph theory#Subgraphs|subgraph]] formed by the edges in <math>X</math> and <math>c</math> is the number of connected components of the same subgraph.<ref name="tutte65"/> The corank of the graphic matroid is known as the [[circuit rank]] or cyclomatic number.