For (finite or infinite) undirected, simple graphs $G, H$, let

$V_{\text{Hom}} = \{f:G\to H:f\text{ is a graph homomorphism}\}$, and $E_{\text{Hom}} =\big\{\{f,g\}\subseteq V_{\text{Hom}}: \{f(v),g(v)\} \in E(H) \text{ for all } v\in V(G)\big\}.$

We set $\text{Hom}(G,H) = (V_{\text{Hom}}, E_{\text{Hom}})$.

Given any graph $G$, are there always graphs $H_1, H_2$ with more than $1$ point each such that $G\cong \text{Hom}(H_1, H_2)$?

EDIT. Thanks to Vidit for spotting the $1$-point solution solving the problem trivially, so I have excluded this.

  • 1
    $\begingroup$ I suspect that for finite $G$, this holds for most graphs $H_1$ with $|V(H_1)|\gg|V(G)|$ and $H_2=G\square H_1$ (heuristically, for random $H_1$ there should be no maps $H_1\to G\square H_1$ other than the obvious ones). For infinite $G$, the question may involve some nontrivial set theory--for instance, if $G$ is a complete infinite graph, it is easy to see that $H_1$ and $H_2$ must have greater cardinality than $G$. $\endgroup$ May 1, 2015 at 19:33
  • $\begingroup$ @EricWofsey What does the box in "$G$ box $H$" mean? $\endgroup$ May 7, 2015 at 2:48
  • $\begingroup$ @ViditNanda: The Cartesian product of graphs, which is adjoint to the Hom described in the question. $\endgroup$ May 7, 2015 at 2:52

1 Answer 1


Warning: the following statement answers an older version of this question.

Let $G$ be the graph you want to realize. Then, $\text{Hom}(\bullet,G) \simeq G$ where $\bullet$ is the graph containing one vertex and no edges.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.