Cycle basis

In graph theory, a branch of mathematics, a cycle basis of an undirected graph is a set of simple cycles that forms a basis of the cycle space of the graph. That is, it is a minimal set of cycles that allows every Eulerian subgraph to be expressed as a symmetric difference of basis cycles.

A fundamental cycle basis may be formed from any spanning tree or spanning forest of the given graph, by selecting the cycles formed by the combination of a path in the tree and a single edge outside the tree. Alternatively, if the edges of the graph have positive weights, the minimum weight cycle basis may be constructed in polynomial time.

In planar graphs, the set of bounded cycles of an embedding of the graph forms a cycle basis. The minimum weight cycle basis of a planar graph corresponds to the Gomory–Hu tree of the dual graph.

A spanning subgraph of a given graph G has the same set of vertices as G itself but, possibly, fewer edges. A graph G, or one of its subgraphs, is said to be Eulerian if each of its vertices has even degree (its number of incident edges). Every simple cycle in a graph is an Eulerian subgraph, but there may be others. The cycle space of a graph is the collection of its Eulerian subgraphs. It forms a vector space over the two-element finite field. The vector addition operation is the symmetric difference of two or more subgraphs, which forms another subgraph consisting of the edges that appear an odd number of times in the arguments to the symmetric difference operation.

...
Wikipedia