# All Science Fair Projects

## Science Fair Project Encyclopedia for Schools!

 Search    Browse    Forum  Coach    Links    Editor    Help    Tell-a-Friend    Encyclopedia    Dictionary

# Science Fair Project Encyclopedia

For information on any area of science that interests you,
enter a keyword (eg. scientific method, molecule, cloud, carbohydrate etc.).
Or else, you can start by choosing any of the categories below.

# Minor (graph theory)

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 G1, G2,... of finite graphs is given, then there always exists two indices i < j such that Gi is a minor of Gj.

In linear algebra, there is a different unrelated meaning of the word minor. See minor (linear algebra).

03-10-2013 05:06:04