Minor (graph theory)
From Wikipedia, the free encyclopedia
- In linear algebra, there is a different unrelated meaning of the word "minor". See minor (linear algebra).
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 contractions on a subgraph of G. Edge contraction is the process of removing an edge and identifying its two endpoints. Contracting a loop is equivalent to deleting it.
In the following example, graph H is a minor of graph G:
H. 
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.
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 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 G1, G2,... of finite graphs is given, then there always exists two indices i < j such that Gi is a minor of Gj.
