Editing Matroid (section)

===Matroids from graph theory===
A second original source for the theory of matroids is [[graph theory]].

Every finite graph (or [[multigraph]]) <math>G</math> gives rise to a matroid <math>M(G)</math> as follows: take as <math>E</math> the set of all edges in <math>G</math> and consider a set of edges independent if and only if it is a [[tree (graph theory)|forest]]; that is, if it does not contain a [[simple cycle]]. Then <math>M(G)</math> is called a ''cycle matroid''. Matroids derived in this way are ''[[graphic matroid]]s''. Not every matroid is graphic, but all matroids on three elements are graphic.<ref name=Ox13/> Every graphic matroid is regular.

Other matroids on graphs were discovered subsequently:

*The [[bicircular matroid]] of a graph is defined by calling a set of edges independent if every connected subset contains at most one cycle.

*In any directed or undirected graph <math>G</math> let <math>E</math> and <math>F</math> be two distinguished sets of vertices.  In the set <math>E</math>, define a subset <math>U</math> to be independent if there are <math>|U|</math> vertex-disjoint paths from <math>F</math> onto <math>U</math>.  This defines a matroid on <math>E</math> called a ''[[gammoid]]'':<ref name=Ox115/> a ''strict gammoid'' is one for which the set <math>E</math> is the whole vertex set of <math>G</math>.<ref name=Ox100>{{harvp|Oxley|1992|p=100}}</ref>

*In a [[bipartite graph]] <math>G = (U,V,E)</math>, one may form a matroid in which the elements are vertices on one side <math>U</math> of the bipartition, and the independent subsets are sets of endpoints of [[Matching (graph theory)|matchings]] of the graph. This is called a ''transversal matroid'',<ref name=Ox4648>{{harvp|Oxley|1992|pp=46–48}}</ref><ref name=Wh877297>{{harvp|White|1987|pp=72–97}}</ref> and it is a special case of a gammoid.<ref name=Ox115>{{harvp|Oxley|1992|pp=115}}</ref>  The transversal matroids are the [[dual matroid]]s to the strict gammoids.<ref name=Ox100/>

*Graphic matroids have been generalized to matroids from [[signed graph]]s, [[gain graph]]s, and [[biased graph]]s.  A graph <math>G</math> with a distinguished linear class <math>B</math> of cycles, known as a "biased graph" <math>(G, B)</math>, has two matroids, known as the ''frame matroid'' and the ''lift matroid'' of the biased graph.

: If every cycle belongs to the distinguished class, these matroids coincide with the cycle matroid of <math>G</math>. If no cycle is distinguished, the frame matroid is the bicircular matroid of <math>G</math>. A signed graph, whose edges are labeled by signs, and a gain graph, which is a graph whose edges are labeled orientably from a group, each give rise to a biased graph and therefore have frame and lift matroids.

*The [[Laman graph]]s form the bases of the two&nbsp;dimensional [[rigidity matroid]], a matroid defined in the theory of [[structural rigidity]].

*Let <math>G</math> be a connected graph and <math>E</math> be its edge set. Let <math>I</math> be the collection of subsets <math>F</math> of <math>E</math> such that <math> G - F </math> is still connected. Then <math> M^*(G)</math>, whose element set is <math>E</math> and with <math>I</math> as its class of independent sets, is a matroid called the ''bond matroid'' of <math>G</math>.

: The rank function <math>r(F)</math> is the [[cyclomatic number]] of the subgraph induced on the edge subset <math>F</math>, which equals the number of edges outside a maximal forest of that subgraph, and also the number of independent cycles in it.