For graphs $G$ and $H$, let $h(G,H)$ denote the number of graph homomorphisms from $G$ to $H$. Fix some enumeration $G_1,G_2,\ldots$ of (isomorphism classes of) the set $\mathbf{D}$ of finite graphs, which contains only one representative from each isomorphism class. The right $\mathbf{D}$-profile of a graph $G$ is the infinite vector $(G \to \mathbf{D}) := (h(G,G_1),h(G,G_2),\dots)$.

Is it true that $(G\to \mathbf{D}) = (H\to \mathbf{D})$ iff $G \simeq H$?

The analogous left-profile is important in the theory of graph limits. Lovász showed that $(\mathbf{D}\to G) = (\mathbf{D}\to H)$ iff $G \simeq H$.

  • L. Lovász, Operations with structures, Acta Mathematica Hungarica 18(3), 1967, 321–328. doi:10.1007/BF02280291 (reprint)

It is also possible to restrict $\mathbf{D}$ to be a smaller set, for instance just the complete graphs. In this case, right-profile equivalence implies that $G$ and $H$ have the same chromatic polynomials. A conjecture of Bollobás, Pebody and Riordan about the chromatic polynomial implies that this is enough to show isomorphism for almost all graphs, although they also showed that it is likely to be nontrivial to construct examples of non-isomorphic graphs $G$ and $H$ which have the same right-profiles with respect to the set of complete graphs.

One can also ask whether there is a set of target graphs (strictly smaller than the set $\mathbf{D}$ of all graphs) that can be used to determine graph isomorphism; clearly this would imply my question. If such a set is well-known, then I would appreciate a hint or pointer.

  • B. Bollobás, L. Pebody, O. Riordan, Contraction-deletion invariants for graphs, JCTB 80, 2000, 320–345. doi:10.1006/jctb.2000.1988

There are at least two related MO questions: Complete graph invariants? and Invariants that might determine a graph up to isomorphism although these address a somewhat different question.

  • $\begingroup$ Just so I get clear: we are talking graphs as digraphs with loops? and homomorphisms are certain maps of vertex sets? So that h(G,H)=1 and h(H,G)=0, with G being a graph having only one edge between its two vertices and H has only one loop on one of its two vertices? I can imagine the answer being different if homomorphisms were (based on) edge maps. Gerhard "Mucking With The Details Again" Paseman, 2013.06.04 $\endgroup$ Commented Jun 4, 2013 at 21:07
  • $\begingroup$ There is also the issue of (v,u) in G COND (h(u),h(v)) in H, where COND could be either implies or iff, depending on how you like your graph map h from G to H. Gerhard "Rusty In Dealing With Relationships" Paseman, 2013.06.04 $\endgroup$ Commented Jun 4, 2013 at 21:14
  • $\begingroup$ Usual notion of homomorphism, as in the Lovász paper: $u~v$ implies $f(u)~f(v)$. People don't seem to worry about loops and multi-edges in this context because it often seems easy to translate between the graph/multigraph cases with small tweaks. $\endgroup$ Commented Jun 5, 2013 at 0:16

1 Answer 1


It is true. It's Exercise 11 on page 128 of "Algebraic Graph Theory", by Royle and somebody. If I recall correctly (and I might not) the trick is to show that the number of homomorphisms determines the number of injective homomorphisms. [EDIT: as Andras notes, I should have said surjections.]

The result is quite old, and I am somewhat surprised that it's not in the paper of Lovász you cite.

  • $\begingroup$ The "trick" is (for the left profile) in a retelling of Lovasz's result ("Algebras, Lattices, Varieties", Chapter 5). It is not clear to me that a corresponding trick exists for the right profile. Are you sure the exercise applies to the right profile? (It seems likely the same trick should work, but the light has yet to dawn on me.) Gerhard "Thinks Electric Bill Got Paid" Paseman, 2013.06.04 $\endgroup$ Commented Jun 4, 2013 at 22:49
  • $\begingroup$ One switches sides, so one has to use surjections for the right-profile. When the number of surjective homomorphisms is always equal, then the graphs are isomorphic. So one just has to show that this holds when the right-profiles are identical. Partition the homomorphisms into those that are surjective on every subgraph of the target. The number of homomorphisms is the same, and the proper subgraphs lead to equal numbers by an inductive argument; the number of surjective homomorphisms is the difference, which is then equal for the two graphs. $\endgroup$ Commented Jun 5, 2013 at 0:12
  • $\begingroup$ It's Exercise 11 in my copy :). $\endgroup$ Commented Jul 13, 2016 at 0:28
  • $\begingroup$ @DavidE.Roberson; yes, Exercise 11 in mine too. Thanks, I'm fixing it. $\endgroup$ Commented Jul 13, 2016 at 0:31
  • 1
    $\begingroup$ As I was reading the answer I was like, how can this guy know the exercise number and the page but can't recall the second author's name? Took me a second. $\endgroup$
    – Alon Amit
    Commented Jul 13, 2016 at 3:52

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.