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.

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.

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.

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.

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

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

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.