Nesta página, discutiremos o quão parecida a relação de subgrafo (bem como a de subgrafo induzido) é com uma relação de ordem. Afinal, alguns axiomas de ordem são satisfeitos pela noção de subgrafo: um grafo é subgrafo de si mesmo, e, se $G_1$ é subgrafo de $G_2$ e $G_2$ é subgrafo de $G_3$, tem-se que $G_1$ é subgrafo de $G_3$. Porém, a propriedade anti-simétrica não é trivialmente verificada. Isto é, se $H$ é subgrafo de $G$ e $G$ é subgrafo de $H$, tem-se necessariamente que $H = G$?

Para respondermos a essa pergunta, é preciso estabelecer melhor as noções de igualdade e continência entre grafos. Nesse sentido, dizemos que uma função $\varphi : V(H)\to V(G)$ é um mergulho de um grafo $H$ em um grafo $G$ se é injetora e preserva arestas. Mais precisamente, $\varphi(u)\varphi(v)\in E(G)$ sempre que $uv\in E(H)$. Essa definição formaliza apropriadamente quando podemos dizer que $H$ é um subgrafo de $G$: basta que exista $\varphi: V(H) \to V(G)$ um mergulho. Nesse caso, escrevemos ainda $H\leq G$. A figura a seguir exemplifica esse conceito.

Nesse esboço, observe que uma aresta foi adicionada à imagem de $H$ pelo mergulho, isto é, apesar de encararmos $H$ como subgrafo de $G$, essa aplicação não nos permite enxergá-lo como subgrafo induzido. Por esse motivo, estabelecemos uma definição mais exigente. Dizemos agora que $\varphi : V(H)\to V(G)$ é um mergulho forte de um grafo $H$ em um grafo $G$ se é uma aplicação injetora que preserva arestas e não arestas. Ou seja, se $\varphi(u)\varphi(v)\in E(G)$ se, e somente se, $uv\in E(H)$. Nesse caso, escrevemos $H\unlhd G$ e destacamos que $G[\varphi(H)]$ pode ser visto como uma cópia de $H$ induzida em $G$. Em particular, todo mergulho forte é um mergulho. Com isso, adaptando a figura acima, temos o seguinte exemplo de um mergulho forte:

Inclusive, a definição de mergulho forte nos permite estabelecer quando dois grafos $G$ e $H$ são iguais. Assim, escrevemos $H = G$ se existe $\varphi : V(H) \to V(G)$ um mergulho forte que é sobrejetor (e, portanto, bijetor). Nesse caso, $\varphi$ é dito ser um isomorfismo de grafos, bem como sua inversa $\varphi^{-1}$.

Com todo esse vocabulário, podemos apropriadamente discutir o quão anti-simétricas são as relações $\leq$ e $\unlhd$. Para isso, dizemos que dois grafos $G$ e $H$ são gêmeos se $H \leq G$ e $G \leq H$, bem como são gêmeos fortes se $H \unlhd G$ e $G \unlhd H$. Em particular, a aplicação identidade em $V(G)$ verifica que $G$ é gêmeo e gêmeo forte de $G$ para qualquer que seja o grafo $G$. A unicidade desse gêmeo, inclusive, é garantida por sua eventual finitude:

Demonstração: Dado que os grafos $G$ e $H$ são gêmeos, podemos fixar $\varphi : V(G) \to V(H)$ e $\psi : V(H) \to V(G)$ um par de mergulhos mútuos. Observamos ainda que $\varphi$ e $\psi$, por preservarem arestas, induzem naturalmente aplicações $\varphi' : E(G) \to E(H)$ e $\psi' : E(H) \to E(G)$. Mais precisamente, podemos definir $\varphi'(uv) = \varphi(u)\varphi(v) \in E(H)$ para toda aresta $uv \in E(G)$, bem como $\psi'(uv) = \psi(u)\psi(v)\in E(G)$ para toda aresta $uv \in E(H)$. Inclusive, a injetividade de $\varphi$ e $\psi$ garante que $\varphi'$ e $\psi'$ são também injetoras. Ou seja, as aplicações $\varphi$, $\varphi'$, $\psi$ e $\psi'$ são injetoras, verificando que $|V(G)|\leq |V(H)|$, $|E(G)|\leq |E(H)|$, $|V(H)|\leq |V(G)|$ e $|E(H)|\leq |E(G)|$ respectivamente. Portanto, $|V(G)| = |V(H)|$ e $|E(G)| = |E(H)|$, de maneira que, pela finitude dos conjuntos $V(G)$ e $E(H)$, tem-se que as aplicações $\varphi$ e $\varphi'$ são, na realidade, bijetoras. Em particular, a bijetividade de $\varphi'$ garante que $\varphi$ preserva arestas e não arestas, caracterizando essa aplicação como um isomorfismo entre $G$ e $H$. Em suma, $G = H$. $\square$

A hipótese da finitude de $G$ na Proposição acima, porém, não pode ser removida. Por exemplo, o produto cartesiano $\mathbb{N}\times \mathbb{N}$ munido com o conjunto de arestas $\{(i,j)(i,j+1), (i,j)(i+1,j) :i,j\in \mathbb{N}\}$ define um grafo $G$ em aspecto de grid. Por meio da adição de um quadrado com apenas um dos vértices em $G$, obtemos um gêmeo (forte, inclusive) de $G$ que não é isomorfo a ele, pois possui três vértices de grau $2$. Aliás, esse argumento nos permite criar infinitos gêmeos de $G$ diferentes, isto é, dois a dois não isomorfos: basta, para cada $n\in\mathbb{N}$, concatenar $n$ quadrados pelos seus cantos superiores direitos e “pendurá-los” pelo vértice $(0,0)$ de $G$.

Como uma construção similar, considere $G$ o grafo bipartido completo $K_{2,\mathbb{N}}$, em que $2 = \{a,b\}$ é um conjunto de dois elementos. Para cada $n\in\mathbb{N}$, defina $G_n$ a partir de $G$ ao adicionarmos um conjunto $\{v_1,v_2,\dots,v_n,v_{n+1}\}$ de $n+1$ vértices de grau $1$ como vizinhos de $a$. Por construção, $G$ se encontra mergulhado em $G_n$, mas qualquer bijeção entre $\mathbb{N}\cup \{v_1,v_2,\dots,v_n\}$ e $\mathbb{N}$ pode ser utilizada para definir um mergulho de $G_n$ e $G$. Logo, $G$ e $G_n$ são gêmeos, mas $G_n \neq G_m$ se $n\neq m$ (pois esses grafos têm quantidades diferentes de vértices de grau $1$). Por outro lado, nenhum grafo de $\{G_n\}_{n\in\mathbb{N}}$ se encontra mergulhado em $G$ por meio de um mergulho forte. Afinal, se $H \unlhd G$, tem-se que $H$ é um subgrafo bipartido completo. Desse modo, se $G \unlhd H$, o subgrafo $H$ deve ser infinito. Ou seja, $H$ é um grafo bipartido completo com uma parte tendo dois elementos e outra tendo infinitos enumeráveis, de maneira que $H = G$.

Por um argumento análogo, um grafo bipartido completo $K_{1,\mathbb{N}}$ - em que $1 = \{a\}$ é um conjunto de um elemento - tem infinitos gêmeos. Para construí-los, basta adicionar vértices de grau $0$ a $K_{1,\mathbb{N}}$ em quantidades arbitrárias. Nesse caso, porém, os gêmeos obtidos não são conexos. Inclusive, $K_{1,\mathbb{N}}$ não possui gêmeos conexos distintos de si. Por outro lado, um raio duplo $R$ é um grafo que não possui gêmeos, sejam eles conexos ou não. Afinal, todo subgrafo de $R$ não isomorfo a ele tem como componentes conexas vértices de grau $0$, caminhos finitos ou raios com uma extremidade de grau $1$.

Em resumo, os grafos apresentados estão sujeitos a uma dicotomia: ou eles não possuem gêmeos distintos de si ou possuem infinitos deles. Curiosamente, até hoje não se sabe se esse padrão é sempre verificado:

Observamos ainda que as quatro afirmações da conjectura acima são independentes, no sentido de que uma não pode ser trivialmente deduzida a partir de outra. Mesmo assim, existem poucos resultados na literatura que apresentam conclusões parciais para esse problema. Originalmente, inclusive, ele foi proposto para árvores por Bonato e Tardif nesse paper. Mesmo nesse caso restrito, a Dicotomia dos Grafos Gêmeos é conhecida como Tree Alternative Conjecture e permanece em aberto.

Nessa página, apresentaremos um resultado positivo para a conjectura ao verificá-la para a classe de grafos rayless, isto é, grafos que não possuem raios como subgrafos. Tal prova foi elaborada por Bonato, Bruhn, Diestel e Sprüssel nesse artigo e faz uso de uma hierarquia que caracteriza essa família de grafos.

Para descrevermos essa hierarquia, é necessário empregar uma recursão transfinita para definir o rank $\mathrm{rk}(G)$ de um grafo $G$. Nesse sentido, defina $\mathrm{rk}(G) = 0$ se $G$ é um grafo finito. Dado $\alpha > 0$ um ordinal, fixe $G$ um grafo que não tem rank definido. Escreveremos então $\mathrm{rk}(G) = \alpha$ se, como na figura abaixo, existir $S\subset V(G)$ um separador finito com a seguinte propriedade:

$$(\dagger) \text{ toda componente conexa de }G\setminus S\text{ é um grafo que tem rank menor que }\alpha. $$

Nesse caso, destacamos que devem haver infinitas componentes conexas em $G\setminus S$. Isso porque, se houvessem apenas $C_1, C_2, \dots, C_n$ finitas componentes conexas em $G\setminus S$, com ranks $\beta_1,\beta_2,\dots,\beta_n$ respectivamente, a união (finita) de $S$ com os separadores dessas componentes verificaria que $\mathrm{rk}(G) \leq \max\{\beta_1,\beta_2,\dots,\beta_n\} < \alpha$. Por meio dessa recursão, não é difícil descrever alguns grafos com rank:

• Os grafos bipartidos completos $K_{1,\mathbb{N}}$ e $K_{2,\mathbb{N}}$ possuem rank $1$, visto que a remoção de suas partes de tamanho finito faz com que as componentes conexas resultantes sejam finitas, possuindo rank $0$.
• A árvore cujos vértices são os elementos do conjunto $\{\emptyset,\{a\}, \{a,b\}: a,b \in \mathbb{N}\}$ e as arestas são dadas pela coleção $\{\emptyset\{a\}, \{a\}\{a,b\} : a,b \in \mathbb{N}\}$ tem rank $2$. Afinal, a remoção do vértice $\emptyset$ faz com que as componentes conexas do grafo resultantes sejam cópias de $K_{1,\mathbb{N}}$, que tem rank $1$ pelo item acima. Mais geralmente, a árvore da figura abaixo, em que apenas as folhas têm grau finito, tem rank $n$:

• Por sua vez, podemos construir um grafo de rank $\omega$ através da substituição de uma $n-$ésima folha do grafo $K_{1,\mathbb{N}}$ por um grafo de rank $n$, mantendo uma aresta entre esse novo grafo é o vértice de grau infinito de $K_{1,\mathbb{N}}$.

Estruturalmente, os grafos que possuem rank descrevem todos os grafos que não possuem raios como subgrafos, conforme aponta a Proposição a seguir. Por esse motivo, os grafos rayless podem se beneficiar de provas indutivas, como a que faremos logo mais.

Demonstração: Inicialmente, suponha que $G$ possui rank. Por indução sobre $\mathrm{rk}(G)$, verificaremos que ele não possui raios. Para tanto, observamos primeiro que isso de fato ocorre se $\mathrm{rk}(G) = 0$, isto é, se $G$ é finito. Caso $\mathrm{rk}(G) >0$, existe $S\subset V(G)$ finito satisfazendo $(\dagger)$, de maneira que toda componente conexa de $G\setminus S$ tem rank menor que o de $G$. Isso garante que $G$ não tem raios: pela finitude de $S$, se existisse $r$ um raio em $G$, uma componente conexa de $r\setminus S$ seria um raio em alguma componente conexa de $G\setminus S$, que é rayless por hipótese indutiva.

Reciprocamente, suponha que $G$ não tem raios como subgrafos. Por outro lado, suponha também que ele não tem rank. Em particular, alguma de suas componentes conexas $C_0$ não tem rank definido. Em $C_0$, fixe um vértice $v_0$. Como $\{v_0\}$ é um separador que não satisfaz $(\dagger)$, existe $C_1$ uma componente conexa de $C_0\setminus v_0$ que também não tem rank. Fixe $v_1$ um vizinho de $v_0$ qualquer em tal componente. Como antes, $\{v_1\}$ não satisfaz a propriedade $(\dagger)$, existindo $C_2$ uma componente conexa de $C_1\setminus v_1$ que não tem rank. Em suma, se maneira indutiva, é possível construir uma sequência de grafos conexos $\{C_n\}_{n\in\mathbb{N}}$ e de vértices $\{v_n\}_{n\in\mathbb{N}}$ com as seguintes propriedades:

• $v_n \in C_n$ para todo $n \in \mathbb{N}$.
• $v_{n+1}$ é um vizinho de $v_n$ em uma componente conexa $C_{n+1}$ de $C_n\setminus v_n$.
• $C_n$ não tem rank para todo $n\in\mathbb{N}$.

Contudo, $\{v_n\}_{n\in\mathbb{N}}$ descreve um raio em $G$, o que é um absurdo. $\square$

Além de hierarquizar os grafos rayless, a noção de rank se revela últil por admitir certas estimativas elementares:

Demonstração: A prova da primeira afirmação é indutiva, observando que $\mathrm{rk}(H) = \mathrm{rk}(G) = 0$ se $G$ é um grafo finito e $H$ é um de seus subgrafos (sendo, portanto, também finito). Se $\mathrm{rk}(G) > 0$, fixe $S\subset V(G)$ um separador finito com a propriedade $(\dagger)$. Se $H$ é um subgrafo de $G$, destacamos que toda componente conexa de $H\setminus S$ está contida em uma componente conexa de $G\setminus S$. Então, por hipótese indutiva, toda componente conexa de $H\setminus S$ tem rank menor que o de $G$. Em particular, o rank de $H$ existe e $\mathrm{rk}(H) \leq \mathrm{rk}(G)$.

Para provarmos a segunda afirmação, observamos que $G\setminus X$ tem rank pelo enunciado $1$. Se $S\subset V(G)\setminus X$ satisfaz $(\dagger)$ para o grafo $G\setminus X$, tem-se que toda componente conexa de $G\setminus (X\cup S)$ tem rank menor que $\mathrm{rk}(G\setminus X)$. Porém, como $S\cup X$ é finito, isso verifica também que $\mathrm{rk}(G) \leq \mathrm{rk}(G\setminus X)$. Dado que $\mathrm{rk}(G\setminus X) \leq \mathrm{rk}(G)$ também pelo item anterior, obtemos que $\mathrm{rk}(G\setminus X) = \mathrm{rk}(G)$.

Para provarmos a terceira afirmação, suponha por absurdo que existem $S_1,S_2\subset V(G)$ finitos e minimais satisfazendo $(\dagger)$, mas com $S_1\neq S_2$. Em particular, pela minimalidade desses dois separadores, tem-se que $S_1 \setminus S_2 \neq \emptyset$ e $S_2\setminus S_1 \neq \emptyset$. Denote por $\mathcal{C}$ a família de componentes conexas de $G\setminus S_1$, de modo que todas elas possuem rank menor que $\alpha := \mathrm{rk}(G)$ (pois $S_1$ satisfaz $(\dagger)$). Inclusive, fixe $C_1,C_2,\dots,C_n \in \mathcal{C}$ as finitas dessas componentes que possuem elementos de $S_2$.

Tomando $v\in S_1\setminus S_2$ qualquer, a minimalidade de $S_1$ nos garante que a componente conexa $C$ de $G\setminus (S_1\setminus \{v\})$ que contém o vértice $v$ tem rank $\alpha$. Contudo, $C\setminus S_2$ é um subgrafo de $G\setminus S_2$. Assim, como $S_2$ satisfaz $(\dagger)$, a componente conexa $C'$ desse subgrafo que contém $v$ deve ter um rank $\beta < \alpha$. Porém, as componentes conexas de $G\setminus (S_1\cup S_2\setminus \{v\})$ são $C'$ e certos subgrafos de $C_1,C_2,\dots,C_n$. Logo, ao unirmos $S_1\cup S_2\setminus \{v\}$ com (finitos) separadores de $C',C_1,\dots,C_n$ que satisfazem a propriedade $(\dagger)$, obteremos um separador de $G$ que verifica que $\mathrm{rk}(G) \leq \max\{\beta, \mathrm{rk}(C_1),\mathrm{rk}(C_2),\dots,\mathrm{rk}(C_n)\} < \alpha$, o que é uma contradição. $\square$

Com a noção de núcleo, por sua vez, é possível encontrar conjuntos fixos por mergulhos mútuos em grafos rayless gêmeos. Mais precisamente, temos:

Demonstração: Se $G$ e $H$ são gêmeos e $\varphi : V(G)\to V(H)$ e $\psi : V(H)\to V(G)$ são mergulhos mútuos que verificam isso, podemos identificar $G$ e $H$ com os subgrafos (não necessariamente induzidos) $\varphi(G)$ e $\psi(H)$ de $H$ e $G$ respectivamente. Em particular, $\mathrm{K}(\varphi(G)) = \varphi(\mathrm{K}(G))$ e $\mathrm{K}(\psi(H)) = \psi(\mathrm{K}(H))$.

Como $\psi(H)$ é subgrafo de $G$ e $\varphi(G)$ é subgrafo de $H$, o Lema anterior nos garante que $\mathrm{rk}(H) \leq \mathrm{rk}(G)$ e $\mathrm{rk}(G)\leq \mathrm{rk}(H)$. Isto é, $\mathrm{rk}(G) = \mathrm{rk}(H)$. Mais do que isso, $\varphi(G) \cap \mathrm{K}(H)$ satisfaz $(\dagger)$ e verifica que $G = \varphi(G)$ tem um rank, bem como $\psi(H)\cap \mathrm{K}(G)$ satisfaz $(\dagger)$ para verificar que $H = \psi(H)$ tem rank. Logo, pela minimalidade dos núcleos, tem-se que $\mathrm{K}(\psi(H)) \subset \psi(H)\cap \mathrm{K}(G) \subset \mathrm{K}(G)$ e $\mathrm{K}(\varphi(G)) \subset \varphi(G)\cap \mathrm{K}(H) \subset \mathrm{K}(H)$. Em resumo, $\varphi(\mathrm{K}(G))\subset \mathrm{K}(H)$ e $\psi(\mathrm{K}(H))\subset \mathrm{K}(G)$. Visto que as funções $\psi$ e $\varphi$ são injetoras e os separadores $\mathrm{K}(G)$ e $\mathrm{K}(H)$ são finitos, essas continências são, na realidade, igualdades. $\square$

A partir de agora, introduziremos algumas notações convenientes para verificar a Dicotomia dos Grafos Gêmeos para a classe dos grafos rayless. Essa principal demonstração se baseará numa indução no rank do grafo, mas, para que ela seja bem sucedida, é necessário que a hipótese indutiva seja ligeiramente mais forte que a tese que queremos a princípio. Por esse motivo, dados $G$ e $H$ grafos e distinguidos dois suconjuntos finitos de vértices $X\subset V(G)$ e $Y\subset V(H)$, convencionamos que:

• Um mergulho do par $(G,X)$ no par $(H,Y)$, denotado por $\varphi : (G,X) \to (H,Y)$, é um mergulho $\varphi : V(G) \to V(H)$ como definido anteriormente, mas com $\varphi(X)\subset Y$.
• Um mergulho forte do par $(G,X)$ no par $(H,Y)$, denotado por $\varphi : (G,X) \to (H,Y)$, é um mergulho forte $\varphi : V(G) \to V(H)$ como definido anteriormente, mas com $\varphi(X)\subset Y$.
• Os pares $(G,X)$ e $(H,Y)$ são gêmeos se existem mergulhos de pares $\varphi : (G,X)\to (H,Y)$ e $\psi : (H,Y)\to (G,X)$. Nesse caso, a finitude de $X$ e $Y$ nos garante que $\varphi(X) = Y$ e $\psi(Y) = X$.
• Os pares $(G,X)$ e $(H,Y)$ são gêmeos fortes se existem mergulhos fortes de pares $\varphi : (G,X)\to (H,Y)$ e $\psi : (H,Y)\to (G,X)$. Novamente, a finitude de $X$ e $Y$ nos garante que $\varphi(X) = Y$ e $\psi(Y) = X$.
• Os pares $(G,X)$ e $(H,Y)$ são isomorfos se existe $\varphi : V(G) \to V(H)$ um isomorfismo com $\varphi(X) = Y$, denotado também por $\varphi: (G,\overline{X})\to (H,\overline{Y})$.

No caso de $(G,X)$ e $(H,Y)$ serem pares gêmeos, a Proposição acima nos garante que, se $\varphi : (G,X) \to (H,Y)$ e $\psi : (H,Y)\to (G,X)$ são mergulhos mútuos, então, mais do que $\varphi(X) = Y$ e $\psi(Y) = X$, tem-se que $\varphi(X\cup \mathrm{K}(G)) = Y\cup \mathrm{K}(H)$ e $\psi(Y\cup \mathrm{K}(H)) = X\cup \mathrm{K}(G)$. Por esse motivo, denotamos $\overline{X} = X\cup \mathrm{K}(G) $ e $\overline{Y} = Y\cup \mathrm{K}(H)$. Mais do que isso, como $(\psi \circ \varphi)|_{\overline{X}}$ é uma injeção (e portanto uma bijeção) do conjunto $\overline{X}$ sobre si mesmo, existe $n \in \mathbb{N}$ de modo que $(\psi \circ \varphi)^n$ é a aplicação identidade em $\overline{X}$. Logo, a menos de trocar o mergulho $\psi : (H,Y)\to (G,X)$ por $(\psi \circ \varphi)^{n-1}\circ \psi$, podemos sempre supor que $\varphi|_{\overline{X}}$ e $\psi|_{\overline{Y}}$ são aplicações inversas uma da outra.

Similarmente, suponha que exista uma bijeção $\eta : X \to Y$ entre os subconjuntos $X\subset V(G)$ e $Y\subset V(H)$. Dizemos assim que os pares $(G,X)$ e $(H,Y)$ são $\eta-$equivalentes se existe $\varphi : (G,X) \to (H,Y)$ um isomorfismo de grafos tal que $\varphi|_X = \eta$. Nesse caso, abusando da notação, escrevemos $(G,X)\simeq_{\eta} (H,Y)$ e $(H,Y)\simeq_{\eta^{-1}}(G,X)$.

Mais especificamente, se $G$ é um grafo rayless e $X\subset V(G)$ é um conjunto finito qualquer, denotamos por $\mathcal{C}_G$ a família dos grafos da forma $G[C\cup \overline{X}]$, em que $C$ é uma componente conexa de $G\setminus \overline{X}$. Note que, como $\mathrm{K}(G)\subset\overline{X}$, todas essas componentes têm rank menor que $\mathrm{rk}(G)$, bem como os elementos de $\mathcal{C}_G$ propriamente. A figura abaixo exemplifica como são os elementos de $\mathcal{C}_G$.

Fixado $A\in \mathcal{C}_G$, representaremos por $I_G(A)$ a coleção de todos os outros grafos de $\mathcal{C}_G$ que são $\textrm{id}-$equivalentes a $A$, em que $\mathrm{id}:\overline{X}\to\overline{X}$ é a aplicação identidade. Explicitamente, $I_G(A) = \{D\in\mathcal{C}_G : (A,\overline{X})\simeq_{\mathrm{id}}(D,\overline{X})\}$ e a definição desse conjunto nos é relevante por permitir caracterizar quando dois pares $(G,\overline{X})$ e $(H,\overline{Y})$ são isomorfos:

Antes de demonstrarmos esse Lema propriamente, descreveremos seu enunciado de uma forma mais informal. Ele diz que, para que os pares $(G,\overline{X})$ e $(H,\overline{X})$ sejam isomorfos, é suficiente (além de necessário) que exista um isomorfismo que identifica os grafos finitos $G[\overline{X}]$ e $H[\overline{Y}]$ e que a quantidade de cópias de um elemento $A\in \mathcal{C}_G$ em $\mathcal{C}_G$ é, por meio dessa identificação $\eta$, igual a quantidade de suas cópias em $\mathcal{C}_H$. A figura abaixo exemplifica essa descrição.

Demonstração do Lema: Primeiramente, suponha que existam $\eta$ e $\alpha$ como no enunciado. Em particular, para cada $A\in \mathcal{C}_G$, é possível encontrar um isomorfismo de grafos $\varphi_A : V(A) \to V(\alpha(A))$ tal que $\varphi_A|_{\overline{X}} = \eta$. Com isso, defina um isomorfismo $\varphi : V(G) \to V(H)$ pondo $\varphi(v) = \eta(v)$ se $v\in \overline{X}$ e $\varphi(v) = \varphi_A(v)$ se o elemento de $\mathcal{C}_G$ que contém o vértice $v\in V(G)\setminus \overline{X}$ é $A$. Observamos que a bijetividade de $\varphi$ é garantida pela bijetividade de $\alpha$.

Reciprocamente, suponha que existe $\varphi : (G,\overline{X})\to (H,\overline{Y})$ um isomorfismo de grafos. Naturalmente, consideramos $\eta = \varphi|_{\overline{X}}$. Além disso, definimos $\alpha : \mathcal{C}_G\to \mathcal{C}_H$ pondo, para todo $A\in \mathcal{C}_G$, $\alpha(A)$ como o único elemento de $\mathcal{C}_H$ que contém os vértices de $\varphi(A)$. A boa definição de $\alpha$, assim como sua bijetividade, segue diretamente do fato de que $\varphi$ é um isomorfismo de grafos. Além disso, tem-se que, para todo $A\in \mathcal{C}_G$ e todo $D\in I_G(A)$, o seguinte diagrama comuta:

Logo, $\alpha(D)\in I_H(\alpha(A))$. Da mesma forma, se $D\in I_H(\alpha(A))$, tem-se que $\alpha^{-1}(D) \in I_G(A)$. Isso verifica, portanto, que $|I_G(A)| = |I_H(\alpha(A))|$, para qualquer que seja $A\in\mathcal{C}_G$. $\square$

Finalmente, podemos enunciar o resultado parcial da Dicotomia dos Grafos Gêmeos que estamos interessados em abordar. Para tanto, apenas destacamos que um par $(G,X)$ - em que $G$ é um grafo e $X\subset V(G)$ é finito - é dito ser conexo se $G\setminus X$ é um grafo conexo. Nesse sentido, temos:

Antes de inicarmos a demonstração, observamos que, ao fazermos $X=Y=\emptyset$, obtemos exatamente o enunciado da Dicotomia dos Grafos Gêmeos, exceto pelas afirmações referentes a gêmeos fortes. Entretanto, a demonstração do Teorema acima para o caso em que $(H,Y)$ é um gêmeo forte do par $(G,X)$ e a ele não isomorfo, permitindo-nos obter infinitos gêmeos fortes não isomorfos desses pares, é similar à que será apresentada e foi feita nesse artigo já referenciado.

Demonstração: A demonstração será feita por indução no rank do grafo $G$, observando que, no caso em que $\mathrm{rk}(G) = 0$, esse grafo é finito e, portanto, não possui gêmeos diferentes de si. Suponha então que $\mathrm{rk}(G) > 0$ e que o resultado se verifica para grafos de rank menor.

Inicialmente, abordaremos o caso em que algum elemento $C_0 \in \mathcal{C}_G$ é tal que $(C_0,\overline{X})$ possui um gêmeo conexo não isomorfo a si. Pela hipótese indutiva, portanto, existe $\{(C_i,X_i): i\in \mathbb{N}\}$ uma família infinita de gêmeos conexos distintos do par $(C_0,\overline{X})$. Conforme destacamos anteriormente, é possível identificar $X_i$ e $\overline{X}$ por meio de mergulhos mútuos de $(C_i,X_i)$ e $(C,\overline{X})$ que são inversos um do outro quando restritos a $X_i$ e $\overline{X}$. Agora, considere $\mathcal{T}$ a coleção de todos os elementos de $\mathcal{C}_G$ da forma $(A,\overline{X})$ que são $\mathrm{id}-$equivalentes a $(C_0,\overline{X})$ ou gêmeos desse par. Definindo um grafo rayless $G_i$, troque cada elemento de $\mathcal{T}$ por uma cópia de $(C_i,\overline{X})$. Observamos que $(G_i,X)$ é conexo se $(G,X)$ o era. Mais do que isso, é possível mergulhar $(G_i,\overline{X})$ em $(G,\overline{X})$ e vice versa por meio de:

• Aplicações identidades em $\overline{X}$ e nas componentes de $\mathcal{C}_G\setminus \mathcal{T}$, que foram mantidas na definição de $G_i$.
• Isomorfismos ou mergulhos mútuos entre $(G_i,\overline{X})$ e elementos de $\mathcal{T}$, cujas existências são garantidas pela própria definição de $\mathcal{T}$.

A figura abaixo exemplifica como são tomados esses mergulhos mútuos, concluindo que os pares $(G_i,\overline{X})$ e $(G,\overline{X})$ são gêmeos para todo $i\in \mathbb{N}$.

Pela definição de $\mathcal{T}$, por sua vez, um isomorfismo $\varphi : V(G_i)\to V(G_j)$ entre $(G_i,\overline{X})$ e $(G_j,\overline{X})$ não pode induzir em $\overline{X}$ a aplicação identidade se $i\neq j$. Caso contrário, esse isomorfismo levaria elementos de $\mathcal{T}$ de $(G_i,\overline{X})$ em elementos de $\mathcal{T}$ de $(G_j,\overline{X})$, estabelecendo um isomorfismo entre $(C_i,\overline{X})$ e $(C_j,\overline{X})$ (que não existe por hipótese). Consequentemente, $(G_i,\overline{X})$ pode ser isomorfo a apenas finitos outros pares da forma $(G_j,\overline{X})$. Afinal, se houvessem em $\{(G_j,\overline{X}): j \in \mathbb{N}\}$ infinitas cópias de $(G_i,\overline{X})$, infinitos desses isomorfismos, pelo Princípio da Casa dos Pombos, induziriam uma mesma bijeção $\eta : \overline{X}\to \overline{X}$. Entretanto, se $j,k\in\mathbb{N}$ são distintos tais que $(G_i,\overline{X})\simeq_{\eta}(G_j,\overline{X})$ e $(G_i,\overline{X})\simeq_{\eta} (G_k,\overline{X})$, tem-se que $(G_j,\overline{X})\simeq_{\mathrm{id}}(G_k,\overline{X})$, o que é um absurdo. Consequentemente, é possível extrair de $\{(G_i,\overline{X}): i \in \mathbb{N}\}$ uma subfamília infinita $\{(G_{i_n}, \overline{X}):n\in\mathbb{N}\}$ de elementos dois a dois não isomorfos. Isto é, esses pares são infinitos gêmeos distintos de $(G,\overline{X})$. Nessa construção, porém, destacamos que sequer utilizamos o fato de que $(H,\overline{Y})$ é um gêmeo distinto de $(G,\overline{X})$.

Então, a partir de agora é possível supor que nenhum elemento de $\mathcal{C}_G$ possui um gêmeo distinto de si. Da mesma maneira, podemos supor que nenhum elemento de $\mathcal{C}_H$ possui um gêmeo diferente de si. Dessa vez, fixe $\varphi : (G,\overline{X})\to (H,\overline{Y})$ e $\psi : (H,\overline{Y})\to (G,\overline{X})$ um par de mergulhos mútuos, supondo ainda que $(\psi \circ \varphi)|_{\overline{X}}$ é a função identidade. Assim, defina a função shift em $G$ como a aplicação $\mathfrak{s}_G : \mathcal{C}_G \to \mathcal{C}_G$ que leva uma componente conexa $(C,\overline{X})$ na (única) componente conexa $(D,\overline{X})$ tal que $(\psi\circ\varphi)(C)\subset D$. Da mesma forma, considere o shift em $H$ como a aplicação $\mathfrak{s}_H : \mathcal{C}_H \to \mathcal{C}_H$ que mapeia um par $(C,\overline{Y})\in\mathcal{C}_G$ no (único) par $(D,\overline{Y})\in\mathcal{C}_H$ tal que $(\varphi \circ \psi)(C)\subset D$. Nesse contexto, mostraremos que vale uma das seguintes afirmações:

1. Existe $(A,\overline{X})\in\mathcal{C}_G$ que não é $\mathrm{id}-$equivalente a $(\mathfrak{s}_G(A),\overline{X})$. Além disso, se $\mathcal{A}$ é a coleção (não vazia, portanto) de todos os elementos de $I_G(A)$ que não são $\mathrm{id}-$equivalentes a seu shift, podemos tomar $|\mathcal{A}| = |I_G(A)|$ caso $I_G(A)$ seja infinito.
2. Existe $(A,\overline{Y})\in\mathcal{C}_H$ que não é $\mathrm{id}-$equivalente a $(\mathfrak{s}_H(A),\overline{Y})$. Além disso, se $\mathcal{A}$ é a coleção (não vazia, portanto) de todos os elementos de $I_H(A)$ que não são $\mathrm{id}-$equivalentes a seu shift, podemos tomar $|\mathcal{A}| = |I_H(A)|$ caso $I_H(A)$ seja infinito.

Por um momento, suponha que nenhuma dessas afirmaçoes se verifica. Em particular, dado $A\in \mathcal{C}_G$ - a menos de trocá-lo por um elemento de $I_G(A)\setminus \mathcal{A}$ - podemos supor que ele é $\mathrm{id}-$equivalente a seu shift. Isto é, existe $\gamma : (A,\overline{X})\to (\mathfrak{s}_G(A),\overline{X})$ um isomorfismo de grafos que é a aplicação identidade quando restrito a $\overline{X}$. Se $D\in \mathcal{C}_H$ é tal que $\varphi(A)\subset D$, porém, $\varphi : (A,\overline{X})\to (D,\overline{Y})$ e $\gamma^{-1}\circ \psi : (D, \overline{Y})\to (A,\overline{X})$ são mergulhos mútuos. Isto é, $(A,\overline{X})$ e $(D,\overline{Y})$ são grafos gêmeos, devendo ser iguais (pois estamos analisando o caso em que nenhum elemento de $\mathcal{C}_G$ tem gêmeo distinto de si). Consequentemente, não pode haver $B\in I_G(A)\setminus \{A\}$ de forma que $\varphi(B)\subset \varphi(A)$. Caso contrário, $\varphi(A)\setminus \overline{X}$ e $\varphi(B)\setminus \overline{X}$ seriam cópias disjuntas (não induzidas) do grafo $A\setminus \overline{X}$ em $D\setminus \overline{Y}$, pois $\varphi$ é uma aplicação injetiva. Porém, $D\setminus \overline{X}$ é isomorfo ao próprio grafo $A\setminus \overline{X}$, mostrando que $A\setminus \overline{X}$ é um grafo conexo que contém duas cópias disjuntas de si mesmo, devendo ter um raio.

Em resumo, essa argumentação verifica que $\varphi$ leva elementos distintos de $I_G(A)\setminus \mathcal{A}$ em elementos distintos de $I_H(D)$. Isto é, $|I_G(A)| = |I_G(A)\setminus \mathcal{A}| \leq |I_H(D)|$. Por simetria, então, obtém-se também que $|I_H(D)|\leq |I_G(A)|$. Ou seja, verificamos que, para todo $A\in \mathcal{C}_G$, a quantidade de elementos de $\mathcal{C}_G$ que são $\textrm{id}-$equivalentes a $A$ é a mesma quantidade de elementos de $\mathcal{C}_H$ que também o são (por meio da identificação $\varphi|_{\overline{X}}: \overline{X}\to \overline{Y})$. Pelo Lema da Decomposição de Isomorfismos, portanto, $(G,\overline{X})$ e $(H,\overline{Y})$ devem ser isomorfos, contradizendo a principal hipótese sobre esses pares.

Portanto, sem perda de generalidade, podemos assumir que a primeira afirmação se verifica. Se $A$ e $\mathcal{A}$ são como dados por ela, mostraremos que a órbita $\{\mathfrak{s}_G^n(D)\}_{n \geq 1}$ não intersecta $I_G(A)$, para todo $D\in\mathcal{A}$. Por um momento, suponha que isso não ocorre. Logo, existe $n \geq 1$ tal que $(A,\overline{X})\simeq_{\mathfrak{id}} (\mathfrak{s}_G^n(D),\overline{X})$. Isto é, existe $\varphi : (A,\overline{X})\to (\mathfrak{s}_G^n(D),\overline{X})$ um isomorfismo de grafos que é a identidade se restrito a $\overline{X}$. Uma vez que $\mathfrak{s}_G(D)\notin I_G(A)$ pela definição de $\mathcal{A}$, devemos ter $n \geq 2$. Ainda, como $D\in \mathcal{A}\subset I_G(A)$, fixe $\psi : (D,\overline{X})\to (A,\overline{X})$ um isomorfismo com $\psi|_{\overline{X}} =\mathrm{id}$. Nesse caso, contudo, $\mathfrak{s}_G \circ \psi^{-1}: (A,\overline{X})\to (\mathfrak{s}_G(D),\overline{X})$ e $\varphi^{-1}\circ \mathfrak{s}_G^{n-1}: (\mathfrak{s}_G(D),\overline{X})\to (A,\overline{X})$ são mergulhos que atestam que $(A,\overline{X})$ e $(\mathfrak{s}_G(D),\overline{X})$ são gêmeos. Pelo caso que estamos analisando, porém,$(A,\overline{X})$ e $(\mathfrak{s}_G(A),\overline{X})$ devem ser isomorfos. Como o isomorfismo que atesta isso pode ser escolhido de forma a ser idêntico em $\overline{X}$, contradizemos a escolha de $D$ como elemento de $\mathcal{A}$.

Com base nessa observação, iremos decompor a coleção $\mathcal{C}_G$ nos seguintes três conjuntos:

• $\mathcal{A}$ é como na sentença $1$ anterior.
• $\mathcal{A}^-$ denota a coleção de elementos $D \in \mathcal{C}_G$ tais que $\mathfrak{s}_G^n(D)\in I_G(A)$ para algum $n\geq 1$. Em particular, pela definição de $\mathcal{A}$, tem-se que $I_G(A)\setminus \mathcal{A}\subset \mathcal{A}^-$.
• $\mathcal{A}^+ = \mathcal{C}_G\setminus (\mathcal{A}\cup \mathcal{A}^-)$. Ou seja, elementos de $\mathcal{A}^+$ são os elementos de $\mathcal{C}_G$ que não são $\mathrm{id}-$equivalentes a $A$ e que nunca o serão pela composição iterada de $\mathfrak{s}_G$. Assim, pela escolha de $\mathcal{A}$ e pela observação do parágrafo anterior, tem-se que $\mathfrak{s}_G(A)\subset \mathcal{A}^+$. Também decorre imediatamente da definição de $\mathcal{A}^+$ sua invariância pelo shift, isto é, $\mathfrak{s}_G(\mathcal{A}^+)\subset \mathcal{A}^+$.

A figura abaixo esboça essa partição de $\mathcal{C}_G$ e sua relação com a dinâmica do shift.

Além disso, como a aplicação $\mathfrak{s}_G : \mathcal{C}_G \to \mathcal{C}_G$ é um mergulho, podemos definir um novo mergulho $\gamma : (G,\overline{X})\to (G,\overline{X})$ pondo: $\gamma(v) = v$ se $v\in \displaystyle\overline{X}\cup\bigcup_{D\in \mathcal{A}^-}D$ e $\gamma(v) = \mathfrak{s}_G(v)$ se $v\in \displaystyle \bigcup_{D\in \mathcal{A}\cup \mathcal{A}^+}D$. Observe ainda que, como esboçado pela figura abaixo, a imagem de $\gamma$ não intersecta $D\setminus \overline{X}$ se $D\in \mathcal{A}$.

Finalmente, somos capazes de construir gêmeos para $(G,\overline{X})$. Isso, contudo, será feito mediante os dois casos a seguir:

1. Primeiramente, suponha que $I_G(A)$ é um conjunto finito. Nesse caso, defina $G_1$ como o grafo obtido a partir de $G$ com a adição em $\mathcal{C}_G$ de uma cópia $A'$ de $A$ que é $\mathrm{id}-$equivalente a ela por meio de um isomorfismo $\alpha : (A',\overline{X})\to (A,\overline{X})$. Por ser construído a partir de $G$ pela adição de alguns vértices, tem-se naturalmente que $(G,\overline{X})$ está mergulhado em $(G_1,\overline{X})$. Porém, é possível também mergulhar $(G_1,\overline{X})$ em $(G,\overline{X})$, bastando estender $\gamma$ para $A'$ pondo $\gamma(v) = \alpha(v)$ se $v\in A'$. Note que, como $\alpha(A') = A\in\mathcal{A}$, a aplicação $\gamma$ continua sendo injetora. Em resumo, $(G,\overline{X})$ e $(G_1,\overline{X})$ são grafos gêmeos, mas $G_1$ possui uma cópia de $A$ - $\textrm{id}-$equivalente a essa componente - a mais. Ao fazermos essa construção indutivamente, portanto, é possível encontrar $(G_n,\overline{X})$ um par gêmeo de $(G,\overline{X})$ com $n$ cópias a mais da componente $A\in \mathcal{C}_G$. Em particular, pelo Lema da Decomposição de Isomorfismos, é possível extrair de $\{(G_n,\overline{X}): n \geq 1\}$ uma subcoleção infinita de gêmeos dois a dois não isomorfos de $(G,\overline{X})$. Afinal, $(G_n,\overline{X})$ e $(G_m,\overline{X})$ não podem ser isomorfos por um isomorfismo que é a aplicação identidade quando restrita a $\overline{X}$, mas a quantidade de bijeções de $\overline{X}$ em $\overline{X}$ é finita.
2. Suponha agora que $I_G(A)$ é infinito, de modo que $|I_G(A)| = |\mathcal{A}|$. Arbitrariamente, então, fixe $\{A_n\}_{n\in\mathbb{N}}$ uma coleção enumerável de elementos de $I_G(A)$. Assim, para cada $n\in\mathbb{N}$, considere $G_n$ o grafo obtido pela remoção de todas as componentes do conjunto $\{A_m \setminus \overline{X}: m > n\}$. Em particular, se $m$ e $n$ são distintos, tem-se que a quantidade de elementos de $\mathcal{C}_{G_n}$ que são $\mathrm{id}-$equivalentes a $A$ é diferente da quantidade de elementos de $\mathcal{C}_{G_m}$ que o são. Assim, pelo Lema da Decomposição de Isomorfismos, $(G_n,\overline{X})$ e $(G_m,\overline{X})$ não são isomorfos por meio de uma aplicação que é a função identidade quando restrita a $\overline{X}$. Consequentemente, $(G_n,\overline{X})$ é isomorfo a apenas finitos outros elementos de $\{(G_i,\overline{X}) : i \geq 1\}$, sendo possível encontrar $\{(G_{n_i},\overline{X}) : i \in \mathbb{N} \}$ uma coleção infinita de grafos dois a dois não isomorfos. Basta, portanto, mostrarmos que $(G_n,\overline{X})$ é um gêmeo de $(G,\overline{X})$ para todo $n\in\mathbb{N}$. Nessa direção, observamos primeiro que $G_n$ é definido como subgrafo de $G$, existindo naturalmente um mergulho de $(G_n,\overline{X})$ em $(G,\overline{X})$. Agora, fixando $\alpha : I_G(A)\to \mathcal{A}$ uma bijeção qualquer, considere o mergulho $\gamma : (G,\overline{X})\to (G,\overline{X})$ definido da seguinte maneira:
   • $\gamma(v) = v$ se $v\in \overline{X}$ ou $v\in D$ para alguma componente $D\in \mathcal{A}^-\setminus I_G(A)$.
   • $\gamma(v) = \mathfrak{s}_G(v)$ se $v\in D$ para alguma componente $D\in \mathcal{A}\cup \mathcal{A}^+$.
   • $\gamma(v) = \varphi_D(v)$ se $v$ é elemento de uma componente de $I_G(A)\setminus \mathcal{A}$, em que $\varphi_D : (D,\overline{X})\to (\alpha(D),\overline{X})$ é algum isomorfismo de grafos com $\varphi_D|_{\overline{X}} =\mathrm{id}$.

Com isso, observe que $\gamma\left(\bigcup I_G(A)\right) \subset \mathcal{A}\cup \mathcal{A}^+$. Dessa forma, conforme ilustrado pela figura abaixo, a aplicação $\gamma^2$ mergulha o par $(G,\overline{X})$ no par $(G_n,\overline{X})$, para qualquer $n\in\mathbb{N}$. Isso finaliza a verificação de que, para todo $n\in\mathbb{N}$, os pares $(G_n,\overline{X})$ e $(G,\overline{X})$ são gêmeos.

$\square$

Por fim, destacamos que a definição de gêmeo de um grafo se assemelha com uma propriedade de Bernstein-Schröder, em alusão ao seguinte clássico resultado de Fundamentos de Matemática:

Conforme destacado aqui, em diversas áreas da matemática existem problemas que visam estudar se dois objetos são iguais dado que em um se encontra algo semelhante ao outro. Nessa direção, a noção de gêmeo é talvez a que mais se aproxima de uma definição “do tipo Bernstein-Schroeder” na Teoria dos Grafos. Mesmo assim, a título de curiosidade, mencionamos abaixo dois outros resultados relacionados a grafos que podem ser encarados como análogos do Teorema de Cantor-Bernstein-Schroeder.

O primeiro deles diz respeito a quando é possível encarar um conjunto de vértices dentro de outro em um grafo por meio de caminhos disjuntos. Assim como no Teorema de Cantor-Bernstein-Schroeder, uma demonstração do Teorema a seguir pode ser encontrada sem o auxílio do Axioma da Escolha, como feito por Diestel e Thomassen neste paper.

O resultado a seguir, por sua vez, diz respeito a quando é possível encontrar árvores geradoras que, apesar de disjuntas nas arestas, as cobrem:

Esse resultado, que pode ser encontrado aqui, é de autoria de Erde, Gollin, Jóo, Knappe e Pitz. Inclusive, esses autores destacam que, para $\lambda$ é finito, a sentença acima é um problema em aberto.