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

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'.

• Isn't the existence of a bijective homomorphism exactly the definition of an isomorphism (not only for graphs but everywhere)? Could you maybe tell why you think that this might not be the case for graphs? Also important: Are your graphs allowed to be infinite, or are you only considering finite graphs?
– Dirk
Sep 4 '17 at 10:00
• Not if $G$ and $H$ are finite. In order to show that $f_1$ is an isomorphism, it is enough to show that $H$ does not have more edges than $G$. But this follows from the bijectivity of $f_2$. Sep 4 '17 at 10:36
• @DirkLiebhold No, compare to the situation in topology, where the existence of bijective continuous functions in either direction between spaces does not imply homeomorphy: mathoverflow.net/questions/30661/… Sep 4 '17 at 10:49
• @TobiasFritz Thanks for your comment, I could add "infinite" to the question Sep 4 '17 at 10:50
• @DirkLiebhold: To be explicit, let $G_1$ have two vertices $a,b$ and no edges; and let $G_2$ have the same two vertices $a,b$ with an edge between $a$ and $b$. Then the identity map from $G_1$ to $G_2$ is a bijective homomorphism but not an isomorphism. Sep 4 '17 at 14:19

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''$.

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 • 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.)

1. 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)$$.