Editing Spanning tree (section)

==Definitions==
A tree is a [[connected graph|connected]] [[undirected graph]] with no [[cycle (graph theory)|cycles]]. It is a spanning tree of a graph ''G'' if it spans ''G'' (that is, it includes every vertex of ''G'') and is a subgraph of ''G'' (every edge in the tree belongs to ''G''). A spanning tree of a connected graph ''G'' can also be defined as a maximal set of edges of ''G'' that contains no cycle, or as a minimal set of edges that connect all vertices.

===Fundamental cycles===
Adding just one edge to a spanning tree will create a cycle; such a cycle is called a '''fundamental cycle''' with respect to that tree. There is a distinct fundamental cycle for each edge not in the spanning tree; thus, there is a one-to-one correspondence between fundamental cycles and  edges not in the spanning tree.  For a connected graph with ''V'' vertices, any spanning tree will have ''V''&nbsp;−&nbsp;1 edges, and thus, a graph of ''E'' edges and one of its spanning trees will have ''E''&nbsp;−&nbsp;''V''&nbsp;+&nbsp;1 fundamental cycles (The number of edges subtracted by number of edges included in a spanning tree; giving the number of edges not included in the spanning tree). For any given spanning tree the set of all ''E''&nbsp;−&nbsp;''V''&nbsp;+&nbsp;1 fundamental cycles forms a [[cycle basis]], i.e., a basis for the [[cycle space]].<ref>{{harvtxt|Kocay|Kreher|2004}}, pp.&nbsp;65–67.</ref>

===Fundamental cutsets===
Dual to the notion of a fundamental cycle is the notion of a '''fundamental cutset''' with respect to a given spanning tree. By deleting just one edge of the spanning tree, the vertices are partitioned into two disjoint sets. The fundamental cutset is defined as the set of edges that must be removed from the graph ''G'' to accomplish the same partition. Thus, each spanning tree defines a set of ''V''&nbsp;−&nbsp;1 fundamental cutsets, one for each edge of the spanning tree.<ref>{{harvtxt|Kocay|Kreher|2004}}, pp.&nbsp;67–69.</ref>

The duality between fundamental cutsets and fundamental cycles is established by noting that cycle edges not in the spanning tree can only appear in the cutsets of the other edges in the cycle; and ''vice versa'': edges in a cutset can only appear in those cycles containing the edge corresponding to the cutset. This duality can also be expressed using the theory of [[matroid]]s, according to which a spanning tree is a base of the [[graphic matroid]], a fundamental cycle is the unique circuit within the set formed by adding one element to the base, and fundamental cutsets are defined in the same way from the [[dual matroid]].<ref>{{citation |title=Matroid Theory |volume=3 |series=Oxford [[Graduate Texts in Mathematics]] |first=J. G. |last=Oxley |author-link=James Oxley |publisher=Oxford University Press |year=2006 |isbn=978-0-19-920250-8 |page=141 |url=https://books.google.com/books?id=puKta1Hdz-8C&pg=PA141}}.</ref>

===Spanning forests===
A collection of disjoint (unconnected) trees is described as a ''[[Forest (graph theory) | forest]]''.  A ''spanning forest'' in a graph is a subgraph that is a forest with an additional requirement.  There are two incompatible requirements in use, of which one is relatively rare.

* Almost all graph theory books and articles define a spanning forest as a forest that spans all of the vertices, meaning only that each vertex of the graph is a vertex in the forest. A connected graph may have a disconnected spanning forest, such as the forest with no edges, in which each vertex forms a single-vertex tree.<ref name="pearls">{{citation |title=Pearls in Graph Theory: A Comprehensive Introduction|title-link= Pearls in Graph Theory
 |last1=Hartsfield |first1=Nora |last2=Ringel |first2=Gerhard |author2-link=Gerhard Ringel |publisher=Courier Dover Publications |year=2003 |isbn=978-0-486-43232-8 |at=[https://books.google.com/books?id=R6pq0fbQG0QC&pg=PA100 p. 100]}}.</ref><ref>{{citation |title=Combinatorics: Topics, Techniques, Algorithms |first=Peter J. |last=Cameron |author-link=Peter Cameron (mathematician) |publisher=Cambridge University Press |year=1994 |isbn=978-0-521-45761-3 |page=163 |url=https://books.google.com/books?id=_aJIKWcifDwC&pg=PA163}}.</ref>

* A few graph theory authors define a spanning forest to be a maximal acyclic subgraph of the given graph, or equivalently a subgraph consisting of a spanning tree in each [[Connected component (graph theory)|connected component]] of the graph.<ref>{{citation |title=Modern Graph Theory |volume=184 |series=Graduate Texts in Mathematics |first=Béla |last=Bollobás |author-link=Béla Bollobás |publisher=Springer |year=1998 |isbn=978-0-387-98488-9 |page=350 |url=https://books.google.com/books?id=SbZKSZ-1qrwC&pg=PA350}}; {{citation |title=LEDA: A Platform for Combinatorial and Geometric Computing |first=Kurt |last=Mehlhorn |author-link=Kurt Mehlhorn |publisher=Cambridge University Press |year=1999 |isbn=978-0-521-56329-1 |page=260 |url=https://books.google.com/books?id=Q2aXZl3fgvMC&pg=PA260}}.</ref>

To avoid confusion between these two definitions, {{harvtxt|Gross|Yellen|2005}} suggest the term "full spanning forest" for a spanning forest with the same number of components as the given graph (i.e., a maximal forest), while {{harvtxt|Bondy|Murty|2008}} instead call this kind of forest a "maximal spanning forest" (which is redundant, as a maximal forest necessarily contains every vertex).<ref>{{citation |title=Graph Theory and Its Applications |edition=2nd |first1=Jonathan L. |last1=Gross |first2=Jay |last2=Yellen |publisher=CRC Press |year=2005 |isbn=978-1-58488-505-4 |page=168 |url=https://books.google.com/books?id=-7Q_POGh-2cC&pg=PA168}}; {{citation |title=Graph Theory |volume=244 |series=Graduate Texts in Mathematics |first1=J. A. |last1=Bondy |first2=U. S. R. |last2=Murty |publisher=Springer |year=2008 |isbn=978-1-84628-970-5 |page=578 |url=https://books.google.com/books?id=V0gUTxkOSboC&pg=PA578}}.</ref>