If $G$ and $H$ on 3 or more vertices are hypomorphic, don't they have to be isomorphic due to their shared induced subgraphs?

Question

Basically, my reasoning is that any two finite graphs with at least three vertices will have at least three vertex-deleted subgraphs, which are also induced subgraphs. Any two graphs which share at least three of these vertex-deleted subgraphs must be isomorphic. The hypomorphism implies the two graphs share three or more of these subgraphs, so they must be isomorphic.

Terse reasoning

1. If $G$ and $H$ are hypomorphic, then both share the same multi-set of vertex-deleted subgraphs, or $D(G) = D(H)$
2. A graph will have $|V|$ vertex-deleted subgraphs, therefore $|D(G)| \geq 3$ and $|D(H)| \geq 3$
3. If $|D(G) \cap D(H)|=1$, then $G$ and $H$ contain an isomorphic induced subgraph and a single shared missing vertex $v_1$.
4. If $|D(G) \cap D(H)|=2$, then they share the same set of edges which connects $v_1$ to the rest of the induced subgraph, except for a possible edge connecting $v_1$ to $v_2$, the missing vertex from the second vertex-deleted subgraph
5. If $|D(G) \cap D(H)|\geq3$, then $G \simeq H$ as the third vertex-deleted subgraph would contain both $v_1$ and $v_2$, allowing us to deduce whether both graphs have the edge ($v_1$,$v_2$)
6. Finally, because of [2], and the hypomorphism implies that both graphs have the same multi-set (three or more vertex-deleted subgraphs in common), why wouldn't $G \simeq H$?

Answer 1

Well, to start with, here are two graphs that are not isomorphic, even though they have three isomorphic vertex-deleted subgraphs:

If $G$ is the graph on the left and $H$ is the graph on the right, then:

• $G-\{1\}$ and $H - \{a\}$ are both the diamond graph (a $K_4$ missing an edge).
• $G -\{3\}$ and $H - \{b\}$ are both the path graph $P_4$.
• $G - \{5\}$ and $H - \{c\}$ are both the paw graph (a $K_3$ with a leaf added).

Therefore it's not enough to have an overlap of three vertex-deleted subgraphs to conclude that $G$ and $H$ are isomorphic.

So where is the flaw in your argument? The problem that even though the subgraphs above are isomorphic, they are not compatibly isomorphic. If we give vertex $3$ in $G$ and vertex $b$ in $H$ the same name $v_1$, then $G - \{v_1\}$ isomorphic to $H - \{v_1\}$. If we give vertex $5$ in $G$ and vertex $c$ in $H$ the same name $v_2$, then $G - \{v_2\}$ is isomorphic to $H - \{v_2\}$, but in that isomorphism, the vertices we called $v_1$ aren't matched to each other!

So it doesn't make sense to say that $G$ and $H$ are isomorphic except possibly for the edge $v_1v_2$, because we don't know that we can simultaneously agree on which vertex is $v_1$ and which vertex is $v_2$.

---

To illustrate the subtlety of the reconstruction conjecture, here is an example in which $D(G)$ and $D(H)$ agree in all but one element:

• $G-\{1\} \simeq H-\{a\}$.
• $G-\{2\} \simeq H-\{d\}$.
• $G-\{3\} \simeq H-\{c\}$.
• $G-\{5\} \simeq H-\{b\}$.
• $G-\{6\} \simeq H-\{e\}$.
• but $G - \{4\}$ is not isomorphic to $H - \{f\}$...