Minor (graph theory)

From Wikipedia, the free encyclopedia

In graph theory, a graph H is called a minor of the graph G if H is isomorphic to a graph that can be obtained by zero or more edge deletions or edge contractions on a subgraph of G. Edge contraction is the process of removing an edge and combining its two endpoints into a single node (since the edge is first removed, the resulting node has a loop if and only if either one of the original ones have). Alternatively, H is a minor of G if it can be obtained from G by contracting edges, removing edges, and removing isolated nodes.

In the following example, graph H is a minor of graph G:

The following diagram illustrates this. First construct a subgraph of G by eliminating the dashed-lines (and the resulting stranded vertex), and then contract the gray edge (combining the two vertices it connects):

The relation "being a minor of" is a partial order on the isomorphism classes of graphs. As consequence of this fact we may say that, if I is a minor of H and H is a minor of G, then I is a minor of G.

A deep result by Neil Robertson and Paul Seymour states that if any infinite list G₁, G₂,... of finite graphs is given, then there always exist two indices i < j such that G_i is a minor of G_j.

[edit] Minor-closed graph families

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 Wagner's theorem characterizing the planar graphs as the graphs having neither K₅ nor K_3,3 as minors.

Classes of graphs described in this way have the property that every minor of a graph in F is also in F; such a class is said to be minor-closed. The general situation is described by the Robertson-Seymour theorem, stating that any minor-closed family is characterized by a finite set of forbidden minors. If F is minor-closed and does not contain all graphs, then every graph in F must be sparse.

Notable minor-closed graph families include: