MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I was thinking about this question a couple of days ago, and got reminded again by a recent question on graph homomorphisms.

Given a graph $G$, we call two vertices $u,v$ indistinguishable if the map which interchanges $u$ and $v$ and is the identity on the rest of the vertices is an isomorphism. Let $\mathbb{Graph}$ be the underlying quiver of the category of graphs with graph homomorphisms. I.e. the vertices are isomorphism classes of finite graphs, and there are $|Hom(G,H)|$ arrows from $G$ to $H$.

Is it true that $\mathbb{Graph}$ has no pairs of indistinguishable vetices?

share|cite|improve this question
@Tom: Sorry, I meant to ask a simpler question and Chris Godsil below guessed correctly. – Gjergji Zaimi Apr 25 '12 at 2:43
up vote 6 down vote accepted

It's an old result of Lovasz that if $|\mathrm{Hom}(G,X)|=|\mathrm{Hom}(H,X)|$ for all graphs $X$, then $G$ and $H$ are isomorphic. If I understand your quiver correctly, the answer to your question is yes, for the trivial reason that the quiver does not contain a pair of equivalent vertices.

share|cite|improve this answer
Ok, yes, that is the question I meant to ask. What is Lovasz' paper where he proves this? – Gjergji Zaimi Apr 25 '12 at 2:42
It might be in L. Lov ́asz: Direct product in locally finite categories, Acta Sci. Math. Szeged 23 (1972), 319-322. (But it's not that hard to prove.) – Chris Godsil Apr 25 '12 at 3:19
The discussion in seems to imply than an extra technical condition ("twin-freeness") is required. Is this satisfied by the questioner's setup? I can't tell. – Jason Reed Sep 21 '12 at 19:05

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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