Many people I talk to about graph theory feel some uneasiness when it comes to the notion of “minor”. I want to try to alleviate this feeling by providing the definiton of minor that I work with.

First an easy definition. If is a simple, undirected graph and are non-empty and disjoint, we say that are *connected to each other* if there are such that .

Let be simple, undirected graphs. We say that is a **minor** of if there is a collection of non-empty, mutually disjoint, and connected subsets of and a bijection such that

whenever and then the sets and are connected to each other in .

Advertisements