GRAPH MINOR THEORY

Graph Minor Theory is a branch of graph theory that studies the structure of graphs by looking at their minor subgraphs. The theory was developed by Neil Robertson, Paul Seymour, and Robin Thomas.

A minor of a graph is a graph that can be obtained by taking a subgraph and contracting some of its edges. For example, if we take the graph below and contract the edges (2,3), (3,4), and (1,5), we obtain the graph on the right as a minor.

The Graph Minor Theory asserts that every infinite family of graphs contains either a small member or a member that contains a small minor. This result is known as the Graph Minor Theorem and was first proved by Robertson and Seymour in a series of papers.

The Graph Minor Theorem has several important consequences. For example, it implies that the family of planar graphs is well-quasi-ordered, which means that every infinite sequence of planar graphs contains a pair of graphs where one is a minor of the other.

The Graph Minor Theory has also been used to prove other important results, such as the Four Colour Theorem, which states that every map on a plane can be coloured with at most four colours so that no two adjacent regions have the same colour.