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
- If $G$ and $H$ are hypomorphic, then both share the same multi-set of vertex-deleted subgraphs, or $D(G) = D(H)$
- A graph will have $|V|$ vertex-deleted subgraphs, therefore $|D(G)| \geq 3$ and $|D(H)| \geq 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$.
- 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
- 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$)
- 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$?
Best Answer
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:
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: