grafos:inflacao_minor [WikiMat]

Se $G$ é um $IX$, então $P = \{V_{x}|x \in X \}$ é uma partição de $V(G)$ , e escrevemos $X := G \setminus P$ para esta minor de contração de $G$. Se $U = V_{x}$ é o único conjunto de ramificação não “solteiro”, escrevemos $X =: G \setminus U$ , escreva $v_{U}$ para o vértice $x \in X$ com o qual $U$ contrai , e pense no resto de $X$ como um subgrafo induzido de $G$. O 'menor' caso não trivial disso é que $U$ contém exatamente dois vértices formando uma aresta $e$, de modo que $U = e$. Dizemos então que $X = G \setminus e$ surge de $G$ pela contração da aresta $e$. Veja a figura a seguir a contração da aresta $e=xy$ :

Nota

A noção de contração de arestas é mais simples em multigrafos do que em grafos. Se contraímos uma aresta $e=xy$ em um multigrafo $G=(V,E)$ para um novo vértice $v_{e}$, não há mais necessidade de excluir quaisquer arestas além do próprio $e$: arestas paralelas a $e$ tornam-se laços em $v_{e}$, enquanto as arestas $xv$ e $yv$ tornam-se arestas paralelas entre $v_{e}$ e $v$.

Assim, formalmente, $E(G \setminus e) = E \setminus \{e\}$ , e apenas o mapa de incidência $e' \mapsto \{init(e'),ter(e')\}$ de $G$ tem que ser ajustado ao novo vértice definido em $G \setminus e$. Contrair um laço tem, portanto, o mesmo efeito que excluí-lo.

A noção de minor se adapta de acordo. A contração minor $G / P$ definida por uma partição $P$ de $V(G)$ em conjuntos conexos tem precisamente aquelas arestas de $G$ que unem classes de partição distintas. Se houver várias dessas arestas entre as mesmas duas classes, elas se tornarão arestas paralelas de $G / P$. No entanto, normalmente não damos a $G / P$ quaisquer laços resultantes de arestas de $G$ cujas extremidades estejam na mesma classe de partição $U$. Isso nos exigiria dizer quais arestas de $G[U]$ são contraídas (supondo que elas induzam um subgrafo gerador conexo de $G[U]$), ou pelo menos quantas são, o que parece inútil se não nos importamos com laços em $G / P$ de qualquer maneira.

Como a relação de minor é transitiva, toda sequência de deleções ou contrações de vértices ou arestas produz um minor. Por outro lado, cada minor de um dado grafo finito pode ser obtido desta maneira:

Proposição

Sejam $G$ e $H$ grafos finitos. Então $G$ é um minor de $H$ se, e somente se, existem grafos $H = X_0, X_1, \dots, X_n = G$ tais que cada $X_{i+1}$ resulta de $X_i$ através da remoção de um vértice, da remoção de uma aresta ou da contração de uma aresta.

Demonstração. Se $G$ é minor de $H$, então existe um $IG$ subgrafo de $H$. É claro que podemos obter qualquer subgrafo de $H$ através de uma sequência de remoções de vértices e arestas. Basta remover, um por um, cada aresta e cada vértice que não pertencem ao subgrafo em questão. Além disso, note que:

Se um grafo possui alguma aresta, é possível realizar nele uma contração de aresta, reduzindo seu número de arestas;
Uma contração de aresta não pode aumentar o número de componentes conexas de um grafo.

Essas duas propriedades implicam que uma sequência maximal de contrações de arestas em um grafo conexo necessariamente resulta em um único vértice. Utilizando uma tal sequência sobre as inflações dos vértices de $G$ em $IG$, conseguimos desfazer o processo de inflação, obtendo o grafo $G$ (note que arestas não pertencentes às inflações são sempre mantidas).

Segue que $G$ resulta de uma sequência de remoções de vértices e arestas e contrações de arestas partindo de $H$.

$\square$