2
$\begingroup$

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$?
$\endgroup$
1
$\begingroup$

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

enter image description here

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:

enter image description here

  • $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\}$...
$\endgroup$
  • $\begingroup$ Yep, you're right, the second and third isomorphic card don't necessarily imply a complete isomorphism. However, I've realized point [3] in my original post is still correct. If we relabel both graphs based on the shared card $C$, then $G$ and $H$ are only different because of the set of edges ($v_0$, $v_x$), where $v_0$ is the shared missing vertex and $v_{x} \in V_{C}$. Now here's where we can fix my logic above (cont) $\endgroup$ – Naiim May 8 '19 at 5:08
  • $\begingroup$ For both graphs, take every $v_{x} \in V_{C}$, and see if you can find cards in both of their decks that contain the edge ($v_0$, $v_x$). If we can recover the exact same set of endpoints $v_x$, then $G$ and $H$ are isomorphic as they contain a shared induced subgraph on $|V|-1$ vertices, a shared missing vertex, and the same set of endpoints for the vertex (cont) $\endgroup$ – Naiim May 8 '19 at 5:17
  • $\begingroup$ Finally, the only way we could recover the same set of endpoints is by having each card in both decks be $\mathit{compatibly}$ isomorphic with one in the other like you were saying, in other words, there must be a hypomorphism between the two graphs. We again arrive at the same conclusion that a hypomorphism implies an isomorphism, no? $\endgroup$ – Naiim May 8 '19 at 5:27
  • $\begingroup$ How do you tell, when looking at a card, if it contains the edge $(v_0, v_x)$? $\endgroup$ – Misha Lavrov May 8 '19 at 5:28
  • $\begingroup$ The labels we created when we relabeled both graphs according to their shared induced subgraph so that $v_0$ matches for them. The rest of the cards would get relabeled too, then we just look for ($v_0$,$v_x$), for every $v_x$. The labeling helps us match up the two graphs so we can compare the edges rigorously. We know the labeling is possible because of the isomorphism on $|V|-1$ edges $\endgroup$ – Naiim May 8 '19 at 5:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.