If all subgraphs of two graphs are pairwise isomorphic, are the graphs themselves isomorphic

graph theorygraph-isomorphisminfinite-graphs

For two graphs $G,H$ let's write $G\cong H$ if they are isomorphic.

Let's denote the set of all subgraphs of $G$ by $\mathcal S(G)$. Note that $G\in \mathcal S(G)$ and there can be elements $a,b\in \mathcal S(G)$ with $a\cong b$ and $a\neq b$ since we use the subset-subgraph notation (e.g. for simple graphs $G=(V,E),G'=(V',E')$ we have $G\subseteq G'$ iff $V\subseteq V'$ and $E\subseteq E'$).

For two graph membered sets $S,T$ we say $S$ and $T$ are pairwise isomorphic ($S\cong T$) if there exists a bijection $p:S\to T$ such that for all $a\in S$ we have $a\cong p(a)$.

The question: For two graphs $G,H$, does $\mathcal S(G)\cong\mathcal S(H)$ imply $G\cong H$?

My thoughts: Let $p$ denote the bijection between $\mathcal S(G)$ and $\mathcal S(H)$. Since $G\in\mathcal S(G)$, let's think about $p(G)$. I thought this has to map to $H$, which is true if $G$ and $H$ are finite. However, the case is slightly different for infinite graphs. For example:

       x   x                  x   x
G: v0  |   |       H: w0      |   |      
   x---x---x--...     x---x---x---x--...

We have $G\ncong H$, but $G\cong H\setminus w_0$ and $H\cong G\setminus v_0$. So, basically I can image that $\mathcal S(G)\cong\mathcal S(H)$, with $p(G)=H\setminus w_0$ and $p(G\setminus v_0)=H$. I don't know if I can extend $p$ to a complete bijection with the isomorphism property. It seems like there is a catch… For example, if I would just expand the bijection by using the induced subgraphs (let d stand for a deleted vertex):

       d   x   x      p          d   x   x
a:     |   |   |      ->         |   |   |       (using p(G))
   x---x---x---x--...    d---x---x---x---x--...

       d   d   x      p          d   x   x
b:     |   |   |      ->         |   |   |       (using p(G\v0))
   d---x---x---x--...    d---x---x---x---x--...

Here we have $a\cong b$, $a\neq b$ and $p(a)=p(b)$, so this extension doesn't work. I don't know how to go from here.

EDIT: I just noticed my question is close to the reconstruction conjecture. Please note we can delete any vertex OR edge, including none, so we have more information. Is a solution for this easier problem known?

Best Answer

It ain't necessarily so (assuming axiom of choice)...

The Rado graph $R$ is the graph on countably many vertices $V_1,V_2...$ with $V_i$ joined to $V_j$ with probability $\frac{1}{2}$. It is well known that the Rado graph contains all countable graphs as induced subgraphs.

It is also well known that the Rado graph $R$ satisfies the extension property; given any disjoint finite sets of vertices $U$ and $V$ there exists a vertex $z$ which is connected to every vertex in $U$ and to none of the vertices in $V$.

Let $H$ be the graph $R\cup{x}$, i.e. the union of $R$ with a vertex that is not connected to anything. Then $H$ does not satisfy the extension property.

However, every countable graph occurs as a subgraph of $R$ infinitely many times and $R$ is a subgraph of $H$.

An explicit bijection from $\mathcal S(H)$ to $\mathcal S(R)$ can be constructed in the following way. Let $f:\mathbb{N}_0\to\mathcal S(H)$ be an enumeration of a countable subset of the set of all subgraphs of $H$ isomorphic to $H$, without restriction take $f(0)=H$. Now the bijection $p:\mathcal S(H)\to\mathcal S(R)$ with the isomorphism property is given by

$$p(x)=\begin{cases} f(f^{-1}(x)+1)&\text{if }x\in\operatorname{rng}f\\ x&\text{else}\end{cases}$$

So we have $\mathcal S(H)\cong S(R)$ but $H\ncong R$.

Related Question