Editing Graph theory (section)

=== Decomposition problems ===
Decomposition, defined as partitioning the edge set of a graph (with as many vertices as necessary accompanying the edges of each part of the partition), has a wide variety of questions. Often, the problem is to decompose a graph into subgraphs isomorphic to a fixed graph; for instance, decomposing a complete graph into Hamiltonian cycles. Other problems specify a family of graphs into which a given graph should be decomposed, for instance, a family of cycles, or decomposing a complete graph ''K''<sub>''n''</sub> into {{nobreak|''n'' − 1}} specified trees having, respectively, 1, 2, 3, ..., {{nobreak|''n'' − 1}} edges.

Some specific decomposition problems and similar problems that have been studied include:
* [[Arboricity]], a decomposition into as few forests as possible
* [[Cycle double cover]], a collection of cycles covering each edge exactly twice
* [[Edge coloring]], a decomposition into as few [[matching (graph theory)|matching]]s as possible
* [[Graph factorization]], a decomposition of a [[regular graph]] into regular subgraphs of given degrees