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 Answer 1

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$
10
  • $\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, 2019 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, 2019 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, 2019 at 5:27
  • $\begingroup$ How do you tell, when looking at a card, if it contains the edge $(v_0, v_x)$? $\endgroup$ May 8, 2019 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, 2019 at 5:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .