# When is it true that if $G$ is isomorphic to a spanning subgraph of $H$ and vice versa, then $G$ is isomorphic to $H$?

When is it true that if $$G$$ is isomorphic to a spanning subgraph of $$H$$ and $$H$$ is isomorphic to a spanning subgraph of $$G$$, then $$G$$ is isomorphic to $$H$$?

Clearly this is true if $$G$$ and $$H$$ are finite graphs; however, this is not necessarily true for infinite graphs. For instance, let $$G$$ be an infinite clique together with infinitely many isolated vertices and let $$H$$ be two disjoint infinite cliques together with infinitely many isolated vertices. We posed this problem in Corsten, DeBiasio, and McKenney - Density of monochromatic infinite subgraphs II (see Problem 2.12), but since this question seems more basic and is only tangential to our results, I figured I would ask here as well.

Addendum 1: After doing some more digging, I found this related post Non-isomorphic graphs with bijective graph homomorphisms in both directions between them which just asked for examples of such graphs $$G$$ and $$H$$ where $$G$$ and $$H$$ are not isomorphic.

Addendum 2: There was a comment yesterday, which for some reason seems to have been deleted, suggesting the term "co-hopfian graph." I found this paper Cain and Maltcev - Hopfian and co-hopfian subsemigroups and extensions which defines co-hopfian graphs (see the paragraph before Lemma 4.5) as those in which every injective homomorphism from $$G$$ to $$G$$ (i.e. injective endomorphism) is an isomorphism. It's unclear to me if this makes a difference in the characterization, but I now believe my question is equivalent to "Which graphs $$G$$ have the property that every bijective homomorphism from $$G$$ to $$G$$ (i.e. bijective endomorphism) is an automorphism." Sorry to overdo it, but my original question has now become three questions:

1. Which graphs $$G$$ have the property that every injective endomorphism is an automorphism? (equivalently, when is it true that if $$G$$ is isomorphic to a subgraph of $$H$$ and $$H$$ is isomorphic to a subgraph of $$G$$, then $$G$$ is isomorphic to $$H$$?)

2. Which graphs $$G$$ have the property that every bijective endomorphism is an automorphism? (equivalently, when is it true that if $$G$$ is isomorphic to a spanning subgraph of $$H$$ and $$H$$ is isomorphic to a spanning subgraph of $$G$$, then $$G$$ is isomorphic to $$H$$?)

3. Are the answers to 1 and 2 the same?

• It's reasonably easy to find locally finite (but still disconnected) examples via a similar trick. For example if you take $G$ to be the collection of all odd length paths, together with countably many isolated vertices and $H$ to be the collection of all even length paths together with countably many isolated vertices, then they are both isomorphic to a spanning subgraph of the other. Jul 30 '20 at 8:28
• The answers to 1 and 2 are not the same: A ray has injective endomorphisms which are not automorphisms (e.g. map every vertex to its successor), but the only bijective endomorphism is the identity. Jul 30 '20 at 23:11

1. $$G_1$$ has vertices $$u_n, v_n$$ for $$n \in \mathbb Z$$, and edges $$u_nu_{n+1}$$ and $$u_{2n}v_n$$ for $$n \in \mathbb Z$$, and $$u_{2n+1}v_n$$ for $$n \in \mathbb N$$.
2. $$G_2$$ is obtained from $$G_1$$ by removing $$v_0$$.
$$G_1$$ has a bijective endomorphism which is not an isomorphism (defined by $$u_n \mapsto u_{n+2}$$ and $$v_n \mapsto v_{n+1}$$).
On the other hand, the only injective homomorphism from $$G_2$$ to itself is the identity: note that $$v_0$$ is a vertex of degree $$2$$ whose neighbours also have degree $$\leq 2$$, thus $$v_0$$ must be mapped to itself under any injective homomorphism. From there it is not hard to inductively show that the identity is the only injective endomorphism.