Editing Graph minor (section)

==Definitions==
An edge contraction is an operation that removes an edge from a graph while simultaneously merging the two vertices it used to connect. An [[undirected graph]] {{mvar|H}} is a minor of another undirected graph {{mvar|G}} if a [[Graph isomorphism|graph isomorphic]] to {{mvar|H}} can be obtained from {{mvar|G}} by contracting some edges, deleting some edges, and deleting some isolated vertices.  The order in which a sequence of such contractions and deletions is performed on {{mvar|G}} does not affect the resulting graph {{mvar|H}}.

Graph minors are often studied in the more general context of [[matroid minor]]s. In this context, it is common to assume that all graphs are connected, with [[loop (graph theory)|self-loops]] and [[multiple edge]]s allowed (that is, they are [[multigraph]]s rather than simple graphs); the contraction of a loop and the deletion of a [[cut-edge]] are forbidden operations. This point of view has the advantage that edge deletions leave the [[rank (graph theory)|rank]] of a graph unchanged, and edge contractions always reduce the rank by one.

In other contexts (such as with the study of [[pseudoforest]]s) it makes more sense to allow the deletion of a cut-edge, and to allow disconnected graphs, but to forbid multigraphs. In this variation of graph minor theory, a graph is always simplified after any edge contraction to eliminate its self-loops and multiple edges.<ref>{{harvtxt|Lovász|2006}} is inconsistent about whether to allow self-loops and multiple adjacencies: he writes on p.&nbsp;76 that "parallel edges and loops are allowed" but on p.&nbsp;77 he states that "a graph is a forest if and only if it does not contain the triangle {{math|''K''{{sub|3}}}} as a minor", true only for simple graphs.</ref>

A function {{mvar|f}} is referred to as "minor-monotone" if, whenever {{mvar|H}} is a minor of {{mvar|G}}, one has {{math|''f''(''H'') ≤ ''f''(''G'')}}.