Anterioremente, vimos duas relações de contenção fundamentais entre grafos: a relação de 'subgrafo' e a relação de 'subgrafos induzidos'. Nesta seção, encontramos mais duas: a relação 'minor' e a relação 'minor topológico'.

Para tanto, seja $X$ um grafo fixo. Uma subdivisão de $X$ é, informalmente, qualquer grafo obtido de $X$ por 'subdividir' algumas ou todas as suas arestas desenhando novos vértices nessas arestas. Em outras palavras, substituímos algumas arestas de $X$ por novos caminhos entre suas extremidades, de modo que nenhum desses caminhos tenha um vértice interno em $V(X)$ ou em outro novo caminho.

Quando $G$ é uma subdivisão de $X$, também dizemos que $G$ é um $TX$ (o $'T'$ significa 'topológico'. Embora, formalmente, $TX$ denote toda uma classe de grafos, a classe de todas as subdivisões de $X$, costuma-se usar a expressão conforme indicado para se referir a um membro arbitrário dessa classe). Os vértices originais de $X$ são os “vértices de ramificação” de $TX$; seus novos vértices são chamados de “vértices de subdivisão”. Observe que os vértices de subdivisão têm grau $2$, enquanto os vértices de ramificação retêm seu grau de $X$. A partir deste conceito, podemos dar uma definição para o “minor topológico”:

Na imagem abaixo, o grafo $G$ é um $TX$, uma subdivisão de $X$. Como $G \subseteq Y$, isso torna $X$ um minor topológico de $Y$:

Da mesma forma, substituir os vértices $x$ de $X$ por grafos conexos disjuntos $G_{x}$, e as arestas $xy$ de $X$ por conjuntos não vazios de $G_{x}-G_{y}$ arestas, produz um grafo que chamaremos de $IX$ (O 'I“ vem de 'inflação'. Como antes, enquanto $IX$ é formalmente uma classe de grafos, aqueles que admitem uma partição de vértice $\{V_{x} \mid x \in V(X)\}$ conforme descrito mais abaixo, usamos a expressão conforme indicado para nos referir a um membro arbitrário dessa classe).

O processo de inflar um vértice \(u\) de um grafo consiste em substituir \(u\) por um grafo conexo \(F\) conectado a todos (e somente) os antigos vizinhos de \(u\). Mais formalmente, um grafo $G$ é um $IX$ se seu conjunto de vértices admite uma partição $\{V_{x}| x \in V(X)\}$ em subconjuntos conexos $V_{x}$ tais que vértices distintos $x,y \in X$ são adjacentes em $X$ se, e somente se, $G$ contém uma aresta $V_{x}-V_{y}$. Os conjuntos $V_{x}$ são os conjuntos ramificados do $IX$. Inversamente, dizemos que $X$ surge de $G$ contraindo os subgrafos $G_{x}$ e chamamos isso de 'minor de contração' de $Y$.

Assim, $X$ é um minor de $Y$ se, e somente se, existe um mapa $\varphi$ de um subconjunto de $V(Y)$ em $V(X)$ tal que para todo vértice $x \in X$ sua imagem inversa $\varphi ^{-1}(x)$ é conexa em $Y$ e para toda aresta $xx' \in X$ existe uma aresta em $Y$ entre os conjuntos de ramificação $\varphi ^{-1}(x)$ e $\varphi ^{-1}(x')$ de suas extremidades. Se o domínio de $\varphi$ é todo de $V(Y)$, e $xx' \in X$ sempre que $x \neq x'$ e $Y$ tem uma aresta entre $\varphi ^{-1}(x)$ e $\varphi ^{-1}(x')$ (de modo que $Y$ é um $IX$), chamamos $\varphi$ de contração de $Y$ sobre $X$.

Na figura abaixo, o grafo $G$ é um modelo de $X$ em $Y$, o que faz de $X$ um minor de $Y$.