===== Conjectura da Reconstrução =====
Sejam $G, H$ grafos. Uma função $\sigma:V(G)\rightarrow V(H)$ é dita um **hipomorfismo** se $G-v\cong H-\sigma(v)$ para todo $v\in V(G)$. Se existe um hipomorfismo entre $G$ e $H$, estes serão ditos **hipomorfos**.
É claro que todo isomorfismo é um hipomorfismo. Não é verdade, porém, que todo hipomorfismo é um isomorfismo. De fato, caso contrário, dados $G$ grafo e $u, v\in V(G)$, seria verdade que $G-u\cong G-v$ implica em $u$ e $v$ serem similares (isto é, existir automorfismo de $G$ que leva $u$ em $v$), o que não ocorre no exemplo abaixo.
{{ :grafos:nonsimilar-samecard.png?600 |}}
Ainda assim, a existência de um hipomorfismo entre dois grafos finitos e não triviais parece sempre sugerir a existência de um isomorfismo entre os mesmos.
É essa observação que leva o nome de //Conjectura da Reconstrução//.
=== Conjectura da Reconstrução ===
Se dois grafos finitos com pelo menos três vértices são hipomorfos, então os dois são também isomorfos.
A exigência de pelo menos três vértices se dá ao fato de $K_2$ e $\overline{K_2}$ serem hipomorfos, porém não isomorfos. Até então, esse é o único exemplo finito conhecido de grafos com tal propriedade.
O nome da conjectura vem da forma alternativa como foi originalmente enunciada. A apresentamos a seguir:
A **classe de equivalência** de um grafo $G$ é a família $[G]$ de todos os grafos isomorfos a $G$. As classes de equivalência da forma $[G-v]$ de um grafo $G$, com $v\in V(G)$, são ditas **cartas** de $G$. O multiconjunto $D(G) := \{[G-u]: u\in V(G)\}$ de todas as cartas do grafo $G$ é o **baralho** de $G$.
Se $D$ é um baralho (de um grafo $G$), dizemos que um grafo $H$ é uma **reconstrução** de $D$ (ou de $G$) se $D(H) = D$. O baralho $D$ (ou o grafo $G$) será dito **reconstrutível** se todas as suas reconstruções são isomorfas. Dessa forma, a Conjectura da Reconstrução supõe que é sempre possível recuperar um grafo (a menos de isomorfismo) através de seu baralho.
=== Conjectura da Reconstrução ===
Todo grafo finito com pelo menos três vértices é reconstrutível.
No que segue, a menos que se diga o contrário, iremos nos referir apenas a grafos finitos com pelo menos três vértices. Além disso, quando tomados dois grafos hipomorfos $G$ e $H$, considere que $V(G) = V(H)$ e que o hipomorfismo em questão é a identidade. Essa restrição simplifica algumas notações e não produz perda de generalidade na conjectura.
==== Classes Reconhecíveis e Reconstrutíveis ====
Chamamos de **classe de grafos** uma família $\mathcal{F}$ de grafos fechada por isomorfismo, i.e., tal que $G\in\mathcal{F}\implies [G]\subset\mathcal{F}$.
Uma classe de grafos $\mathcal{G}$ é dita **reconhecível** se $G\in \mathcal{G}$ implica em $H\in \mathcal{G}$ para toda reconstrução $H$ de $G$.
Uma classe de grafos $\mathcal{G}$ é dita **reconstrutível** se $G\in \mathcal{G}$ implica em $G$ reconstrutível. É claro que se $\mathcal{G}$ reconstrutível, então é também reconhecível.
__As seguintes classes são reconstrutíveis__
* Grafos regulares
* Grafos desconexos
* Grafos separáveis sem vértices de grau $1$
* Árvores
* Cactos
* Grafos planares maximais
* Grafos exoplanares maximais
* Grafos exoplanares
* Grafos completos multipartidos
__As seguintes classes são reconhecíveis__
* Grafos $k$-conexos
* Subdivisões de grafos $3$-conexos
* Grafos planares
* Grafos perfeitos
==== Parâmetros Reconstrutíveis ====
Grande parte dos parâmetros relevantes sobre grafos identifica classes de equivalência em valores únicos (como o número arestas, número cromático ou número de cruzamento). Quando for esse o caso, o valor do parâmetro em uma classe de equivalência $[G]$ será definido como seu valor em $G$.
Um parâmetro $f$ definido sobre uma classe de grafos $\mathcal{G}$ é dito **reconstrutível** se $f(G) = f(H)$ para toda reconstrução $H$ de $G$ com $G, H\in \mathcal{G}$. Note que, se $\mathcal{G} = f^{-1}[X]$ para uma certa função $f$ e um certo conjunto de valores $X$, então $f$ reconstrutível implica em $\mathcal{G}$ reconhecível.
__Os seguintes parâmetros são reconstrutíveis__
* Número de vértices
* Número de arestas
* Grau de um vértice
* Diâmetro
* Conectividade
* Aresta-conectividade
* Número cromático
* Polinômio cromático
* Polinômio dicromático
==== Lemas Auxiliares ====
=== Lema ===
Se um grafo é reconstrutível, então seu complementar também o é.
=== Lema de Kelly ===
Sejam $F, G$ grafos com $|V(F)| < |V(G)|$. Então o número $s(F, G)$ de subgrafos de $G$ isomorfos a $F$ é reconstrutível.
Sejam $F, G$ grafos com $|V(F)|<|V(G)|$ e $v\in V(G)$. Então o número $s_v(F, G)$ de subgrafos de $G$ isomorfos a $F$ contendo o vértice $v$ é reconstrutível.
=== Lema ===
Sejam $F, G$ grafos com $F$ desconexo. Então o número $s(F, G)$ de subgrafos de $G$ isomorfos a $F$ é reconstrutível.
Se $\mathcal{F}$ é uma classe de grafos e $G$ é um grafo, um subgrafo $F$ de $G$ que pertença à $\mathcal{F}$ será dito $\mathcal{F}$**-subgrafo** de $G$. Se $F$ não está contido propriamente em outro $\mathcal{F}$-subgrafo de $G$, este será dito $\mathcal{F}$**-subgrafo maximal** de $G$. Por exemplo, se $\mathcal{G}$ é a classe dos grafos desconexos e $\mathcal{F}$ é a classe dos grafos conexos, então os $\mathcal{F}$-subgrafos maximais de $G\in\mathcal{G}$ são as suas componentes conexas.
=== Lema de Kelly Generalizado ===
Sejam $\mathcal{G}, \mathcal{F}$ classes de grafos tais que $\mathcal{G}$ é reconhecível e, para todo $G\in\mathcal{G}$, cada $\mathcal{F}$-subgrafo de $G$ é vértice-próprio e está contido em um único $\mathcal{F}$-subgrafo maximal de $G$. Então, para todo $F\in\mathcal{F}$ e todo $G\in\mathcal{G}$, o número $m(F, G)$ de $\mathcal{F}$-subgrafos maximais de $G$ isomorfos a $F$ é reconstrutível.
==== Teoremas ====
=== Teorema ===
Se o grafo $G$ é reconstrutível sempre que $diam(G) = 2$ ou $diam(G) = diam(\overline{G}) = 3$, então todo grafo é reconstrutível.
=== Teorema ===
Se grafos $2$-conexos são reconstrutíveis, então todo grafo é reconstrutível.