"Homomorphism fingerprint" for graphs

Question

Let $G, H$ be simple, undirected graphs without loops. We say that $G, H$ have the same homomorphism fingerprint if $|\text{Hom}(X, G)| = |\text{Hom}(X, H)|$ for all graphs $X$. (By graph homomorphisms I mean edge preserving maps; so for instance $\text{Hom}(X,K_2)=\emptyset$ if $\chi(X) > 2$).

From Lovasz [1] we have the following theorem: If $G, H$ are finite and they have the same homomorphism fingerprint, then $G\cong H$.

Are there non-isomorphic infinite graphs that have the same homomorphism fingerprint?

[1] L. Lovasz, Operations with structures,Acta Math. Hungar. 18(1967), 321–328

Answer 1

In any category, if $G$ and $H$ are objects such that there exist monic maps $G\to H$ and $H\to G$, then $|\text{Hom}(X, G)| = |\text{Hom}(X, H)|$ for all $X$. There are plenty of pairs of non-isomorphic infinite graphs with this property.

Answer 2

For graphs $G, H$, let $G \times H$ denote the graph with vertex set $V(G) \times V(H)$ and such that $(g_0, h_0)$ and $(g_1, h_1)$ are connected by an edge iff $g_0$ and $g_1$ are connected by an edge and $h_0$ and $h_1$ are also connected by an edge. By construction this is the categorical product in the category of graphs we're considering, hence we have a natural isomorphism

$$\text{Hom}(X, G \times H) \cong \text{Hom}(X, G) \times \text{Hom}(X, H).$$

Now let $G$ be the disjoint union of countably many copies $Y_n, n \in \mathbb{N}$ of some auxiliary graph $Y$. I claim that $|\text{Hom}(X, G)|$ is always either empty or infinite, as follows: if $f : X \to G$ is a homomorphism, consider the embedding $[k] : G \to G$ which sends $Y_n$ to $Y_{n+k}$. Then the homomorphisms $[k] \circ f : X \to G$ are distinct for all $k$: they can be distinguished by the smallest index $j$ for which the image of the homomorphism intersects $Y_j$ (which is necessarily $k$ plus the corresponding index for $f$ itself).

Letting $H = G \times G$, and using the fact that infinite cardinalities are equal to their squares (unfortunately this is equivalent to the axiom of choice; probably this can be avoided by picking $H$ more carefully), we conclude that if we can find a graph $Y$ for which $G$ and $G \times G$ are not isomorphic, then we have constructed a counterexample.

We can take $Y$ to be the path graph $P_3$ on $3$ vertices. Then $H$ is the disjoint union of countably many copies of $Y \times Y$, which is a connected graph with $9$ vertices. Hence $G$ and $H$ have connected components of different cardinalities and are not isomorphic.

(The moral of the story is that two infinite cardinalities being equal is a much weaker condition than two finite cardinalities being equal.)