Non-isomorphic graphs with bijective graph homomorphisms in both directions between them

As vertex set, take $V=V'\cup V''$, the disjoint union of two infinite sets.

For $G$, take all edges except those joining pairs of vertices from $V''$.

For $H$, add one extra edge, between a pair of vertices $u,v\in V''$.

Then $G\not\cong H$, since if two vertices of $G$ are adjacent, then at least one of them is adjacent to every vertex, but that is not true for the vertices $u,v$ of $H$.

The identity map on $V$ is a bijective homomorphism $G\to H$.

There is a bijective homomorphism $H\to G$ given by choosing arbitrary bijections $V'\cup\{u\}\to V'$ and $V''\setminus\{u\}\to V''$.

Here are two partial answers:

1. EDIT: (the following is tentative; in light of Jeremy Rickards example, which is vertex-3-connected, and with which I cannot find anything wrong, something must be wrong here; perhaps it is where I leaped to the conclusion that the matroids must be isomorphic) In classical logic, and under the additional hypothesis that both $G$ and $H$ are vertex-3-connected, the answer is no.

One way to prove 1. this is via infinite matroid theory by

• appealing to Theorem 1.1 in Johannes Carmesin: Topological cycle matroids of infinite graphs. European Journal of Combinatorics 60 (2017) 135–150:

• noting that loc. cit. is a theorem of classical logic,

• noting that the contrapositive of the 'Moreover, [...]' in loc. cit. is

If two vertex-3-connected graphs have isomorphic topological cycle matroics, then they are isomorphic.

• noting that the hypothesis of the OP $\color{red}{\text{evidently ensures}}$ ${}^{\text{dubious; I was not thiking carefully here}}$ that the topological cycle matroids are isomorphic, because, so to speak, the matroids 'do not see' putative non-edges-mapped to edges (which the OP's hypotheses at least hypothetically allow).

I do not know whether there are positive examples for what the OP is asking for if both $G$ and $H$ have connectivity 2. (I.e., if both $G$ and $H$ are vertex-2-connected yet both do contain separators of cardinality 2.)

2. Even in intuitionistic logic, we have: Lemma. Under the OP's hypotheses, if at least one of the maps $f$ and $g$ i not a graph-isomorphism, then both $G$ and $H$ are non-forests. (I.e., contain a circuit.)

Proof of the Lemma. Let the data be given as stated. Since the statement is invariant under swapping '$f$' and '$g$', we know that $f$ is not a graph-isomorphism; therefore by definition there exists (I think this step is intuitionistically valid (i.v. for short), it is just the definition of 'graph-homomorphism $f\colon G\to H$ whose underlying set-map $V(G)\to V(H)$ is injective but which is not a graph-isomorphism) a two-set $xy\in\binom{V(G)}{2}$ with $xy\notin E(G)$ yet $f(x)f(y)\in E(H)$. Since $G$ is a tree, there exists a unique $x$-$y$-path $P_{xy}$ in $G$. Since $xy$ is not an edge of $G$, we know that $P_{x,y}$ has at least two edges (I think this step, too, is i.v.). By hypothesis, $f$ maps (and this is intuitionistically valid: $P_{x,y}$ is finite by definition of 'graph-theoretic path, so the image $f(P_{x,y})$ can be constructed) $P_{x,y}$ to a graph-theoretic path $f(P_{x,y})$ in $H$. Since we assumed that $f(x)f(y)$ is an edge of $H$, we have constructed a circuit $f(x) f(P_{x,y})f(y)f(x)$ in $H$. Now we apply the given injective graph-homomorphism $g$ to said circuit to also construct a circuit in $G$. We have now found circuits in both $G$ and $H$, completing the proof.

Corollary. If at least one of the graphs $G$ and $H$ is a trees, then the answer to the OP is no, too.

Corollary. Under classical logic: if the correct answer to the question in the OP is yes, then every example of what the OP is asking for must consist of infinite graphs $G$ and $H$ which both contain at least one separating vertex-set of size 2 and both contain at least one circuit.

I got here via this question and I thought it may be worth sharing the following uncountable family of locally finite examples:

Pick an arbitrary set $S \subseteq \mathbb Z$. The vertex set of the graph $G_S$ is $\mathbb Z \times \mathbb Z$. For the edge set take all "vertical" edges from $(m,n)$ to $(m,n+1)$, horizontal edges $(m,n)$ to $(m+1,n)$ for $n < 0$, and horizontal edges $(s,0)$ to $(s+1,0)$ for $s \in S$; note that no horizontal edges are attached to $(m,n)$ for $n>0$.

As long as $S$ and $S'$ are not shifts/reflections of one another, the graphs $G_S$ and $G_{S'}$ are non-isomorphic. The map $f \colon G_S \to G_{S'}$ can be taken as $(m,n) \mapsto (m,n-1)$.