In graph theory, a graph *H* is called a **minor** of the graph *G* if *H* is isomorphic to a graph that results from a subgraph of *G* by zero or more *edge contractions*. Here, "contracting an edge" means removing the edge and identifying its two endpoints, keeping all other edges. For example, the graph * | *--*--* | * is a minor of * /| *-*--*-*-* |/ * (the outer edges are removed, the long middle edge is contracted). The relation "being a minor of" is a partial order on the isomorphism classes of graphs. Many classes of graphs can be characterized by "forbidden minors": a graph belongs to the class if and only if it does not have a minor from a certain specified list. The best-known example is Kuratowski's theorem for the characterization of planar graphs. The general situation is described by the Robertson-Seymour theorem. Another deep result by Robertson-Seymour states that if any infinite list *G*_{1}, *G*_{2},... of finite graphs is given, then there always exists two indices *i* < *j* such that *G*_{i} is a minor of *G*_{j}. In linear algebra, there is a different unrelated meaning of the word *minor*. See minor (linear algebra). |