Graph minor

We can make new shapes from old ones.

First, you can take parts away. You can delete edges or points.

Next, you can squish parts together. This is called contracting an edge. This makes a new shape called a minor.

We use these to find patterns. Some shapes are easy to draw. Others are much harder. These rules help us know which is which.

Imagine you have a drawing of points and lines. This drawing is called a graph. You can change a graph to make a new one. You can delete some lines or points. You can also squish two points together. This is called contracting an edge.

When you do these things, the new shape is called a minor.

For example, graph H is a minor of graph G.

You can find a minor by removing some parts of the original graph.

Math experts use minors to study graph patterns. A famous rule by Klaus Wagner says we can know if a graph is planar. A planar graph is one you can draw without lines crossing. Wagner found that planar graphs never have certain shapes as minors.

Neil Robertson and Paul Seymour found even more. They proved that every set of graphs has a finite number of tiny, special minors. These are called forbidden minors. If a graph does not have these special shapes, it must belong to a certain group. This helps us understand how complex a graph can be.

A graph is a collection of points connected by lines. In math, we can change these graphs to find smaller patterns inside them. We call these smaller patterns minors. You can find a minor in two ways. First, you can delete some lines or points from the original graph. Second, you can use a trick called edge contraction. This means you pick a line and squish the two points it connects into one single point.

By doing these things, you can turn a large, complex graph into a simpler one.

These operations allow us to see how different shapes are related. If you can turn graph G into graph H using these steps, then H is a minor of G.

The order in which you delete or squish parts does not change the final result. This relationship is very organized. It forms what mathematicians call a partial order. This means there is a clear way to rank graphs based on their structure. If one graph is a minor of another, it is essentially a simpler version of that shape. This helps us categorize many different types of mathematical drawings.

History shows us how deep this idea goes. A mathematician named Klaus Wagner studied these patterns long ago. He discovered a rule for planar graphs. A planar graph is a drawing where no lines cross each other. Wagner proved that a graph is planar only if it does not contain two specific shapes as minors. These special shapes are known as K5 and K3,3. Later, Neil Robertson and Paul Seymour made a huge discovery. They proved Wagner's old idea, which was once a famous conjecture. Their work showed that any set of graphs has only a finite number of these special, forbidden minors.

This discovery by Robertson and Seymour changed how we see graph properties. They proved that if a property stays the same when you delete or squish parts, it is called minor-monotone. For every such property, there is a finite list of forbidden minors. If a graph avoids all the shapes on that list, it must have that property. This is a very powerful tool for testing graphs. It even helps us understand the structure of graphs that are missing certain minors. These graphs are often made by gluing simpler pieces together. This helps us solve hard problems about how many lines a graph can have.

We can also use minors to explore other big mysteries. One such mystery is the Hadwiger conjecture. This idea links the number of colors needed for a graph to the minors it contains. It suggests that if a graph lacks a certain large shape, it can be colored with fewer colors. This is closely related to the famous four-color theorem. There are also other versions of minors, like topological minors or immersion minors. Each version uses different rules for how to change the graph. All these ideas help us map out the vast world of shapes and connections.

In the field of graph theory, a graph is a collection of points, called vertices, connected by lines, called edges. Mathematicians often want to know if one graph contains a simpler version of another within its structure. This relationship is defined through the concept of a graph minor. A graph, let's call it H, is considered a minor of another graph, G, if H can be produced from G through a specific sequence of operations. These operations include deleting edges, deleting vertices, and performing edge contractions.

To understand the mechanism, we must look closely at edge contraction. When you contract an edge, you remove that edge while simultaneously merging the two vertices it once connected into a single vertex. You can also simply delete edges or remove isolated vertices. Interestingly, the order in which you perform these contractions and deletions does not change the final resulting graph. If you can transform G into H using these steps, H is a minor of G.

This process allows researchers to strip away complexity to reveal fundamental underlying structures.

There are several distinct variations of this concept. A topological minor is a specific type where a graph H is a minor if a subdivision of H exists within G. While every topological minor is a minor, the reverse is not always true. Another version is the induced minor, which is obtained by contracting edges after first taking an induced subgraph. Finally, there are immersion minors. These are formed using a "lifting" operation, where two edges connected to a common vertex are replaced by a single edge connecting their other endpoints. This is particularly useful in graph drawing to handle crossing points in non-planar graphs.

The history of this theory is rooted in the work of Klaus Wagner. He provided a famous characterization of planar graphs, which are graphs that can be drawn without any edges crossing. Wagner's theorem states that a graph is planar if and only if it does not contain the complete graph K5 or the complete bipartite graph K3,3 as minors. For many years, mathematicians wondered if this idea of "forbidden minors" applied to all graph properties. This led to the development of the Robertson–Seymour theorem. Neil Robertson and Paul Seymour eventually proved that any property preserved by deletions and contractions can be defined by a finite set of forbidden minors. This result confirmed a long-standing idea known as Wagner's conjecture.

The significance of the Robertson–Seymour theorem is immense in computer science and mathematics. Because the number of forbidden minors is always finite for minor-closed families, it is possible to test if a graph has a certain property in polynomial time. This means the task can be completed relatively efficiently as the graph grows larger. Furthermore, the theory provides deep insights into the density of graphs. For example, if a graph does not contain a specific minor, it must be sparse. This means the number of edges stays within a certain constant multiple of the number of vertices. Specifically, for a fixed minor, the number of edges in a simple minor-free graph is bounded by a linear function of the number of vertices.

One of the most profound connections involves the Graph Structure Theorem. Robertson and Seymour discovered that graphs avoiding a specific minor are not entirely random. Instead, they have a predictable structure. These graphs are essentially formed by gluing together smaller pieces, known as clique-sums. These pieces are slightly modified versions of graphs that can be embedded on surfaces of a certain genus. This connects the abstract study of graph minors directly to topology, the study of shapes and surfaces. It shows that the absence of a specific pattern forces the entire graph to follow a strict geometric organization.

Graph minors also link to some of the most famous unsolved problems in mathematics. The Hadwiger conjecture is a major mystery that relates graph coloring to minors. It proposes that if a graph does not contain a complete graph of a certain size as a minor, it can be colored using a specific number of colors. This conjecture is a massive generalization of the famous four-color theorem. Another notable result is the snark theorem. This theorem states that any bridgeless 3-regular graph that requires four colors for an edge coloring must contain the Petersen graph as a minor. These connections show that the study of minors is central to understanding how connectivity, coloring, and geometry interact in mathematical networks.