**Graph Minor**

In graph theory, an undirected 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*.

The theory of graph minors began with Wagner's theorem that a graph is planar if and only if it does not contain the complete graph *K*_{5} nor the complete bipartite graph *K*_{3,3} as a minor. The Robertsonâ€“Seymour theorem states that the relation "being a minor of" is a well-quasi-ordering on the isomorphism classes of graphs, and implies that many other families of graphs have forbidden minor characterizations similar to that for the planar graphs.

Read more about Graph Minor: Definitions, Example, Major Results and Conjectures, Minor-closed Graph Families, Topological Minors, Immersion Minor, Algorithms

### Famous quotes containing the words graph and/or minor:

“When producers want to know what the public wants, they *graph* it as curves. When they want to tell the public what to get, they say it in curves.”

—Marshall McLuhan (1911–1980)

“There are acacias, a graceful species amusingly devitalized by sentimentality, this kind drooping its leaves with the grace of a young widow bowed in controllable grief, this one obscuring them with a smooth silver as of placid tears. They please, like the *minor* French novelists of the eighteenth century, by suggesting a universe in which nothing cuts deep.”

—Rebecca West (1892–1983)