In many categories such as **Set**, **Group**, **Top** (topological spaces) there is a morphism between any two objects, usually in both directions. (If one object is “empty”, like the empty space, or the empty set, there is the “empty” morphism from to the other object, but not the other way round.)

However in the category **Graph** it is possible that non-empty graphs have no graph homomorphism between them in either direction:

Let be the complete graph on 3 points and let be any triangle-free graph with , for instance the **Grötzsch graph**, which has chromatic number 4.

Since is triangle-free, there is no graph homomorphism and if there were a homomorphism , this map would be an -coloring of for some .

Advertisements