Is it known what fraction (almost all?) of graphs have a trivial endomorphism monoid? I can't seem to find any reference to the question. Maybe it's related to the question: what fraction of graphs have chromatic number equal to their clique number?


The book "Graph Homomorphisms" contains an elegant proof that a random graph admits only the identity endomorphism.

The term to search on is "rigid graph". (This has two different meanings but they are easy to distinguish.)

  • $\begingroup$ Is this the book? Graphs and Homomorphisms amazon.com/… $\endgroup$
    – CoffeeCat
    Dec 14 '14 at 17:58
  • $\begingroup$ Yes, that's it. I also think that if you google a bit you might find some notes online giving the proof. $\endgroup$ Dec 14 '14 at 23:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy