Relações entre minors e minors topológicos
Por fim, temos a seguinte relação entre minors e minors topológicos:
Proposição $(i)$
Todo \(TG\) é também um \(IG\), isto é, todo minor topológico de um grafo é também seu minor.
Demonstração: De fato, a fim de subdividir uma aresta \(e = uv\) de \(G\), basta inflar o vértice \(u\), substituindo-o pelo grafo conexo \((\{a, b\}, \{ab\})\) com \(a\) conectado aos antigos vizinhos de \(u\) e \(b\) conectado a \(v\).
$\square$
Proposição $(ii)$
Se \(\Delta(G)\le 3\), então todo \(IG\) contém um \(TG\), isto é, todo minor de um grafo com grau máximo até \(3\) é topológico.
Demonstração. De fato, considere \(IG\) resultado da inflação de \(u\in G\) para o grafo conexo \(F\).
- Se \(d(u) = 1\), seja \(N(u) = \{a\}\). Então, se \(x\) é o vizinho de \(a\) em \(F\), removendo \(F-x\) de \(IG\) temos um grafo isomorfo a \(G\), logo \(TG\).
- Se \(d(u) = 2\), seja \(N(u) = \{a, b\}\). Então, se \(x, y\) são os vizinhos de \(a, b\) em \(F\), respectivamente, como \(F\) é conexo, existe $P$-caminho entre \(x\) e \(y\), de modo que, removendo \(F-P\) de \(IG\) temos um \(TG\).
- Se \(d(u) = 3\), seja \(N(u) = \{a, b, c\}\). Então, se \(x, y, z\) são os vizinhos de \(a, b, c\) em \(F\), respectivamente, como \(F\) é conexo, existe \(P\)-caminho entre \(x\) e \(y\) e \(Q\) -caminho entre \(z\) e \(P\) (considere o caminho que toca em \(P\) uma única vez), de modo que, removendo \(F-P-Q\) de \(IG\) temos um \(TG\).
$\square$
E agora que conhecemos todas as relações padrão entre gráficos, também podemos definir o que significa incorporar um grafo em outro. Basicamente, uma incorporação de $G$ em $H$ é um mapa injetivo $\varphi :V(G) \to V(H)$ que preserva o tipo de estrutura em que estamos interessados. Assim, $\varphi$ incorpora $G$ em $H$ 'como um subgrafo' se preserva a adjacência dos vértices e 'como um subgrafo induzido' se preserva a adjacência e a não adjacência.
Se $\varphi$ é definido em $E(G)$ bem como em $V(G)$ e mapeia as arestas $xy$ de $G$ para caminhos independentes em $H$ entre $\varphi (x)$ e $\varphi (y)$ , ele incorpora $G$ em $H$ 'como um minor topológico'. Da mesma forma, uma incorporação $\varphi$ de $G$ em $H$ 'como minor' seria um mapa de $V(G)$ para conjuntos de vértices conectados disjuntos em $H$ (em vez de para vértices únicos) de modo que $H$ tenha uma aresta entre os conjuntos $\varphi (x)$ e $\varphi (y)$ sempre que $xy$ for uma aresta de $G$. Outras variantes são possíveis; dependendo do contexto, pode-se desejar definir incorporações 'como um subgrafo gerador', 'como um minor induzido' e assim por diante, da maneira óbvia.