Are there simple, undirected graphs $G, H$ that are non-isomorphic, but there exist graph homomorphisms $f_1: G\to H$ and $f_2: H\to G$ which are bijective set-maps $V(G)\rightarrow V(H)$ and $V(H)\rightarrow V(G)$?
Notes.
By the argument in Tobias Fritz's comment below, $G, H$ have to be infinite.
As suggested by a commenter, one should make it unambiguously clear that here, 'simple, undirected graph'='irreflexive symmetric binary relation on a set'.
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:
One way to prove 1. this is via infinite matroid theory by
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.
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.)
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)$.
