If all subgraphs of two graphs are pairwise isomorphic, are the graphs themselves isomorphic?
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$.
No, we don't need $G \cong H$ to have $\mathcal S(G) \cong \mathcal S(H)$. Whenever $G$ is isomorphic to a subgraph $H_0 \subseteq H$, and $H$ is isomorphic to a subgraph $G_0 \subseteq G$, we will have $\mathcal S(G) \cong \mathcal S(H)$.
(And, of course, the reverse implication holds too, since the bijection will pair $G \in \mathcal S(G)$ with some isomorphic $H_0 \in \mathcal S(H)$, and $H \in \mathcal S(H)$ with some isomorphic $G_0 \in \mathcal S(G)$. So this condition characterizes the pairs $(G,H)$ with $\mathcal S(G) \cong \mathcal S(H)$.)
Suppose that $G_0, H_0$ as above exist. Then to construct a congruence-preserving bijection between $\mathcal S(G)$ and $\mathcal S(H)$, note that for every graph $F$ isomorphic to a subgraph of $G$ or $H$, there is:
- An injection from subgraphs of $G$ isomorphic to $F$ to subgraphs of $H$ isomorphic to $F$: for each subgraph of $G$, take the corresponding subgraph of $H_0$.
- An injection from subgraphs of $H$ isomorphic to $F$ to subgraphs of $G$ isomorphic to $F$: for each subgraph of $H$, take the corresponding subgraph of $G_0$.
By the Schröder–Bernstein theorem, there is a bijection between the two sets, and by combining the bijections for all possible $F$, we get the bijection $p$ we wanted.
In particular, we'll have $\mathcal S(G) \cong \mathcal S(H)$ in your example, or in the slightly simpler example of "half-infinite path" and "half-infinite path with an isolated vertex".
The proof above is not constructive, and maybe needs the axiom of choice (not my area of expertise), but I think that for a simple pair $G$ and $H$, we should be able to write down an explicit bijection, too.