# What's a groupoid? What's a good example of a groupoid? [closed]

Or more specifically, why do people get so excited about them? And what's your favorite easy example of one, which illustrates why I should care (and is not a group)?

## closed as primarily opinion-based by Fernando Muro, Alain Valette, Felipe Voloch, Chris Godsil, abxJan 21 '16 at 6:43

Many good questions generate some degree of opinion based on expert experience, but answers to this question will tend to be almost entirely based on opinions, rather than facts, references, or specific expertise. If this question can be reworded to fit the rules in the help center, please edit the question.

I'm surprised this example hasn't been mentioned already:

The 3x3x3 Rubik's cube forms a group. The 15-puzzle forms a groupoid.

The reason is that any move that can be applied to a Rubik's cube can be applied at any time, regardless of the current state of the cube.

This is not true of the 15-puzzle. The legal moves available to you depend on where the hole is. So you can only compose move B after move A if A leaves the puzzle in a state where move B can be applied. This is what characterises a groupoid.

There's more to be found here.

• Very very nice : but then could you find a physical example like those two but for quasigroup ( for help Def1a : A ternary relation where any two elements impose the third , Def1b is a bordered Latin square also Def1c at en.wikipedia.org/wiki/Quasigroup ) – Jérôme JEAN-CHARLES Oct 3 '10 at 0:21
• I guess if this is true, then passing in (European) football also is more like a groupoid than a group. Only the person with the ball can pass to any teammate (or "negative pass" to any opponent). Yes? – isomorphismes Oct 19 '14 at 20:25
• @isomorphismes I like the football analogy though you'll need a formalisation of football where every play is considered to be invertible. – Dan Piponi Nov 25 '14 at 15:00
• ok, right. So passing in a circle (like the Von Trapp family with Baroness Schräder) would work better than football, where movement up the field and other competitive factors would break the invertibility. – isomorphismes Nov 28 '14 at 20:14
• A similar example is the solitaire problem game Rush Hour at thinkfun.com/mathcounts/play-rush-hour . It is excellent for small children precisely because it is a groupoid -- they don't get stuck, frustrated, and have to start over. – Allen Knutson Oct 22 '15 at 2:56

As other people have mentioned, a groupoid can be defined as a category in which every map is invertible. A groupoid with only one object is exactly a group, and a groupoid in which there are no maps between distinct objects is simply a family of groups.

But there's another class of examples, orthogonal to these ones. Namely: any equivalence relation is a groupoid. In fact, an equivalence relation is exactly a groupoid in which for each object a and object b, there is at most one map from a to b. Concretely, the objects of the groupoid are the elements of the set on which the equivalence relation is defined, and there is a map from a to b iff a is equivalent to b.

(A (small) category with the property that for any objects a and b, there is at most one map from a to b, is the same thing as a preordered set — that is, a set equipped with a reflexive transitive relation, usually denoted \leq.)

• Right. If you want to think of groupoids as generalizations of equivalence relations, then a groupoid is a structure that tells you when two objects are "the same," but where two objects can be "the same" in more than one way. – Qiaochu Yuan Oct 20 '09 at 15:54

Personally, the reason I'm interested in groupoids is something called groupoid cardinality and some other related ideas (the link contains a lot of other links). A motivating idea here is that certain sets X of algebraic objects have the property that ($\sum_{x \in X} 1$) is ugly but ($\sum_{x \in X} \frac 1{Aut(x)}$) is much nicer, and so we should think of this is the "true" cardinality of the set (which is actually a groupoid).

Interesting combinatorial stuff happens when you take this philosophy seriously: for example, the cardinality of the groupoid of finite sets and bijections between them is e. Why is this interesting? It suggests that one reason exponential generating functions are important is that the denominator of n! is an indication that what you're really working with is some kind of structure defined over the groupoid of finite sets and bijections. And indeed, there's an approach to combinatorics called species theory that defines a combinatorial species, such as "binary trees," as a functor from this groupoid to itself. From this information one can extract a generating function, but the really important point here is that constructions such as the sum of generating functions are seen to be "decategorifications" of more fundamental combinatorial constructions, so one can avoid the machinery of working with generating functions by working directly with species instead. A good reference here is Bergeron, Labelle, and Laroux.

• I want to add that this was written several years ago and that I have since found other reasons to care about groupoids. – Qiaochu Yuan Jan 21 '16 at 0:05

A groupoid is a generalization of a group. The easiest definition, IMO, is as a category in which all arrows are isomorphisms. So a group is just a groupoid with one object and arrows the elements of the group.

The best example is the fundamental groupoid of a topological space. Build a groupoid by taking the objects to be the points in the space and an arrow from point x to point y to be equivalence classes of paths from x to y. This genearlizes the idea of the fundamental group.

They are useful and Ronald Brown has a whole project of building higher dimensional group theory using them. The great thing about the fundamental groupoid is that there is a version of Van Kampen that gives the fundamental group of the circle (without using covering space theory as is the standard way to do it using only the fundamental group).

ETA: That link might not be working. Google Ronald Brown's Topology and Groupoids book for a good introduction and motivation.

• it is THE most important example! – Sean Tilson Apr 3 '10 at 0:28

Another answer is that a groupoid is a space which has no homotopy groups in dimension ≥ 2. (Analogously a set is a space which has no homotopy groups in dimension ≥ 1.) They arise from taking (homotopy) orbits of group actions on sets, as well as from categories (by discarding the noninvertible morphisms and then taking the nerve). People care about them because they retain useful homotopical information, analogous to the relationship between Hom and Ext in homological algebra, and also because they're a lot easier to work with than general spaces.

Penrose tilings are beautiful objects, with a lot of symmetry...   but their symmetry group is trivial!

So there's a discrepancy somewhere. The answer is: "groupoids"! The topological groupoid of symmetries of a Penrose tiling is non-trivial, and contains all the information that your intuition might call "symmetry".

The reason it's a groupoid and not a group is the following. Given a Penrose tiling, there are many different tilings that are locally undistinguishable from your original tiling. These are the objects of your groupoid. It becomes a topological groupoid under the topology of "uniform convergence in any bounded domain". The arrows are given by isomorphisms between a given tiling (=object) and a translated or rotated version of itself.

• Andre, is there a reference in which what you just described is explained in more detail? Thanks in advance. – Willie Wong May 9 '10 at 17:09
• Weinstein's "Groupoids: Unifying Internal and External Symmetry" is about roughly this topic: ams.org/notices/199607/weinstein.pdf – Qiaochu Yuan May 10 '10 at 4:26
• Thanks Qiaochu! The article is a bit typo heavy, but still a very nice read. And so Andre's third paragraph makes sense to me now. – Willie Wong May 11 '10 at 16:29

Any vector bundle is a groupoid: you can add and subtract vectors only if they are in the same fibre. Similarly, if you take a vector bundle E → M (or some other fibre bundle) then consider the automorphism bundle Aut(E) → M where a point in Aut(E) above p ∈ M is an automorphism of Ep. This is a groupoid since these automorphisms can only be composed if they lie in the same fibre.

These are discrete groupoids in the sense that there are no morphisms between distinct objects (aka points in the base space). However, they are not discrete topologically as they clearly have topologies! (Which, incidentally, shows that you should be careful when using the statement about groupoids having no homotopy above degree 2: this is a statement about groupoids in Set but groupoids exist enriched in other categories where they can have lots of interesting homotopy). To get a more general groupoid, you can consider the bundle Iso(E) → M × M where a point in Iso(E) above (p,q) ∈ M × M is an isomorphism from Ep to Eq.

One reason for liking groupoids is that they allow you to talk about quotients by group actions without actually having to take the quotient. That's useful because some categories don't have quotients - such as the category of smooth manifolds. So when you have a group G acting on a manifold M you can try to take the quotient M/G but that is quite often not a manifold. So instead you can take the groupoid with objects M and morphisms G × M, where a morphism (g,m) has source m and target gm. Even when the quotient exists, or when you've extended the category to include quotients, this can be much better behaved than the corresponding quotient.

Beyond all the categorical and bundle-like examples already given, you can easily understand groupoids as generalizations of groups in a purely geometrical sense.

If you think of groups as the sets of symmetries of certain geometrical objects, then groupoids are local symmetries of geometrical objects. My favorite example of this consists on taking a manifold M and defining a groupoid G as the set of all the local diffeomorphisms f:U-->V where U and V are open sets of M, with multiplication given by composition of maps (whenever it makes sense).

In addition to the answers already given: Alan Weinstein wrote a nice article for the Notices of the AMS which tries to give some motivating examples:

It seems that in certain situations where taking the quotient by a group action "destroys too much information", working directly with an associated groupoid is more useful. Several of the motivating examples in NCG a la Connes (et al) also seem to fit into this point of view.

• Weinstein's article has the nice feature that the example he gives is related to dynamics (and, more specifically, tiling your bathroom floor). – Emily Peters Oct 19 '09 at 1:27

I (mildly) disagree with David Brown's assertion that a set is an example of a groupoid. Given any set, you can put a groupoid structure on it, even "canonically", but not uniquely canonically. (By way of analogy, you wouldn't say that a set is an example of a topological space, would you?) Thus if I give you a set and tell you the definition of a groupoid, you will probably be able to use that set to define a groupoid, but you might not come up with groupoid that David has in mind.

I want to use this as a jumping off point for my answer: one of the neat things about groupoids is that a lot of times you start with a set $X$, you take some kind of "quotient" of it, and then you are apparently left with a set $Y$ but in a way which feels unpleasant: you feel like there is a loss of information. A lot times, there is a natural groupoid structure on $X$, which has the following features:

(i) It is equivalent to or implied by some other kind of structure you are considering on $X$, so it is not evidently profitable to think of $X$ as a groupoid.

(ii) Passage to the quotient set $Y$ loses some of the evident structure.

(iii) However, if you think of $X$ as a groupoid, then the quotient $Y$ is also a groupoid, and this extra structure is exactly the structure that you were sad to have lost.

Example: Let $G$ be a group and $X$ be a set with an action of $G$. Let $Y = G \backslash X$ be the orbit space. In the passage from $X$ to $Y$ we have apparently "used up" the $G$-structure, but this is not so good: for applications we would like to know the stabilizers of the points of $X$; up to conjugacy, these only depend upon the corresponding point in $Y$ but in passage to $Y$ we seem to have lost that information, which is however very important for "mass formulas" as in Qiaochu's response.

Remedy: realize that any $G$-set is canonically a groupoid: the set of morphisms from $x$ to $x'$ is exactly the set of $g$ in $G$ such that $gx = x'$. Then we can take the quotient of this groupoid by the $G$-action [this can be done generally; in this case it is sufficiently evident what this means that I don't think it will be helpful to say any more about it], so that $X/G$ still has a groupoid structure, in which no two distinct objects have any morphisms between them but that the automorphism group of any single object is isomorphic to the isotropy group of any representative.

See for instance

http://www.maths.qmul.ac.uk/~noohi/papers/WhatIsTopSt.pdf

for a bit more on this perspective.

While the categorical definition of groupoid is the most concise, you can also think of a groupoid as being like a group, except where multiplication is only partially defined, rather than being defined for any pair of elements. Here are a few of my favorite examples:

• Given a vector bundle E, the general linear groupoid GL(E) is the groupoid of linear isomorphisms between fibers. Given a map from Ex -> Ey, and another from Ey' -> Ez, we can only compose them if y=y'. When E is just a vector space over a single point, then this is the usual general linear group. In differential geometry, this gives a very natural way to think about frames and G-structures on a differentiable manifold M: just look at the general linear groupoid GL(TM). G-structures can be understood as subgroupoids: for example, a Riemannian structure corresponds to the orthogonal subgroupoid O(TM), consisting of elements of GL(TM) which are also isometries.

• More generally, given a principal G-bundle, the gauge groupoid consists of G-equivariant maps between fibers. This is useful for talking about connections, holonomy, etc., without having to fix a particular gauge.

• Given a directed graph, one can construct the free groupoid generated by the edges. As a special case, the free group on n elements is generated by the graph with one vertex and n self-loops. (There is also a forgetful functor from groupoids to graphs, which is adjoint to the free functor.)

The first two examples happen to be Lie groupoids, and they have corresponding Lie algebroids, which generalizes the relationship between Lie groups and Lie algebras. Whereas a Lie algebra is a vector space with a bracket between elements, a Lie algebroid is a vector bundle with a bracket between sections (as well as an additional structure called the anchor map). For example, if Q is a principal G-bundle, then the gauge groupoid is (Q x Q)/G, while the corresponding gauge algebroid is TQ/G. This comes in handy in geometric mechanics, particularly in reduction theory. If we have a Lagrangian L: TQ -> R, which is invariant with respect to the action of a Lie group G, then is useful to look at the reduced Lagrangian \ell: TQ/G -> R. There are some subtleties arising from the fact that TQ/G is not a tangent bundle, but it is still a Lie algebroid, so this has motivated the study of mechanics on Lie algebroids.

I never think about groupoids in any technical sense, but my favorite easy example of one can be built out of a separable field extension K/k. It is the category whose points are the subfields of the algebraic closure of k which are k-isomorphic to K. The morphisms between two objects are just the k-isomorphisms between the respective subfields. It's some kind of "Galois groupoid" and it's a group if and only if K/k is a Galois field extension.

• You say "the" algebraic closure, but forget that there is no god given algebraic closure. The algebraic closures of a given field also form a groupoid, where all objects are isomophic. – André Henriques May 9 '10 at 11:07
• More general than either of our examples: let K/k be a field extension and make the category whose objects are abstract extensions of k which are k-isomorphic to K. Morphisms are isomorphisms between these fields. But one could do this with any algebraic structure. The thing I like about restricting to those fields contained in a single algebraic structure is that the silly connection with Galois theory can be made. – Joel Dodge May 9 '10 at 22:17

Contra dance (or square dance) gives us a nice example of a groupoid. The objects are the formations (i.e. the positions of the dancers) and the morphisms are the calls up to homotopy. A choreography (or a dance, if you wish) if a set of composable calls whose product is a morphism between two specific objects.

The holonomy groupoid of a foliation is another example of a useful groupoid

it is described here:

http://www.ams.org/journals/bull/2005-42-01/S0273-0979-04-01036-5/S0273-0979-04-01036-5.pdf

For a singular foliation see http://users.uoa.gr/~iandroul/AS-holgpd-final.pdf

Let me expand a bit on what Dave said.

The Yoneda lemma tells us that given an object $X$ of a category $\mathcal C$, the (covariant, contravariant, whatever) functor $h_X : \mathcal C \to \mathsf{Set}$, which sends an object $Y$ to the set $\mathsf{Hom}(Y,X)$, can be thought of as the "same" as the object $X$. There are many situations in which we are interested in a functor $F : \mathcal C \to \mathsf{Set}$, and we might like to know whether $F$ is isomorphic to $h_M$ for some object $M$, because that reduces the study of $F$ to the study of a single object $M$. In such a case we say that $F$ is represented by $M$. The letter $M$ here, suggestively, stands for "moduli".

Example: Given a group $G$, the functor $BG' : \mathsf{Top} \to \mathsf{Set}$ is the functor which sends a topological space $\mathcal X$ to the set of isomorphism classes of principal $G$-bundles over $\mathcal X$. (You can also do the analogous thing for schemes.)

Example: The functor $M_g' : \mathsf{Sch} \to \mathsf{Set}$ is the functor which sends a scheme $X$ to the set of isomorphism classes of flat families of genus $g$ curves over $X$.

In both of the above examples, there is no object $M$ for which $h_M$ is isomorphic to the functor. So this is perhaps not so nice. But, without getting into too many details, there is a natural "fix", namely we can instead consider the functor $BG : \mathsf{Top} \to \mathsf{Groupoid}$ (resp. $M_g : \mathsf{Sch} \to \mathsf{Groupoid}$) which sends a topological space (resp. a scheme) to the groupoid of $G$-bundles (resp. flat families of genus $g$ curves). This groupoid has objects $G$-bundles and morphisms isomorphisms of $G$-bundles (resp. the obvious analogous thing). The original set-valued functor is just the composition of this functor with the functor $\mathsf{Groupoid}$ to $\mathsf{Set}$ which takes a groupoid and returns the set of isomorphism classes of objects in the groupoid.

Anyway, despite the fact that the set-valued functors are not so "geometric", since they are not represented by a "geometric" object (topological space and scheme, respectively), the groupoid-valued functors are more "geometric". In the case of $M_g$, the "geometric" structure we get is that of a "Deligne-Mumford stack", which essentially means that we can for practical purposes pretend that it is represented by a scheme with only some slightly "weird" properties. In the case of $BG$ (the topological one) you can take a "geometric realization" and recover the classifying space $BG$ that we know and love.

Another very important reason for studying groupoids and another very important class of groupoids comes from, as others have already mentioned, group actions. When a group acts on a manifold or a variety, the naive quotient may be badly behaved, for example it may no longer be a manifold (e.g. it might not be smooth, or it might not be Hausdorff) or respectively a variety (or it may not even be clear how to take the quotient at all!), which makes it harder to study geometric properties of the alleged "quotient". However, the groupoid viewpoint allows us to get a better handle on the quotient and its geometry. More precisely, if $G$ is a group acting on a space (manifold, scheme, variety, whatever) $X$, then the "correct" quotient is actually the functor $X/G : \mathcal C \to \mathsf{Groupoid}$ (where $\mathcal C$ is the category of manifolds, schemes, whatever) which sends an object $Y$ to the groupoid of pairs ($G$-bundles $E$ over $Y$, $G$-equivariant morphism from the total space of $E$ to $X$). The functor $BG$ is a special case of this; it's $\mathrm{pt}/G$.

There's some further discussion on this sort of stuff at the nLab:

http://ncatlab.org/nlab/show/moduli+space

http://ncatlab.org/nlab/show/classifying+space

A set is an example of a groupoid, and I care about groupoids as a generalization of sets as opposed to groups. My most fundamental tool is Yoneda's lemma, which says that one can think of a category C as being embedded in the category C-hat of presheaves (C-hat := Hom(C,Sets)); this is a really useful way to think for instance about the category of Schemes (which is special because instead of presheaves you actually get sheaves). Similarly, if you want to think about things like algebraic groups, it is extremely useful to consider Hom(Schemes,Grps) instead.

A stack is a generalization of the notion of a scheme, which one would like to think of as a functor from schemes to groupoids; this doesn't quite work (one only gets a `pseudofunctor') and the notion of a stack is a gadget that makes this work. Just as with algebraic groups, sometime you want the target of the functor that your geometric object represents to have the type of extra structure that your geometric object has; groupoids come up for me in moduli theory, where they keep track of extra automorphisms, or when trying to construct quotients by group actions, where you can keep track of stabilizers.

So not a very precise answer, but also not a technical one, so maybe it will be useful.

To follow on from what Qiaochu said, one of the interesting things about groupoids is their cardinality. Whereas the cardinality of a set is a natural number, the cardinality of a groupoid is a positive rational. This gives us a combinatorial way to inject "numbers" into an abstract system.

For example, a way to think of matrices of natural numbers is just taking spans of finite sets, A <- S -> B. The "numbers" come from counting the paths from A, through S, to B. Composition by pullback then just amounts to matrix multiplication. Incidentally, this is one of the nicest ways to think about commutative bi-alebras, but that's another story (see Stephen Lack - "Composing PROPs" if you're interested).

However, if you take spans of finite groupoids instead, you get computation with matrices of positive rational numbers. If you take spans of "nice" infinite groupoids, you get positive real numbers. John Baez and co. have a nice paper, called Higher-Dimensional Algebra VII: Groupoidification, that works a lot of this out an applies it to quantum physics. It's one of the things that convinced me that groupoids were pretty cool gadgets.

One reason why people get existed about groupoids which has not been mentioned so far: The category of reduced smooth orbifolds is isomorphic to a category of proper effective etale Lie groupoids. For some investigations on orbifolds, working with their local charts can become very clumpsy. Sometimes, the corresponding question on groupoids has an elegant solution.

• A note for readers: it's better to use the 2-category of groupoids, suitably localised, than the 1-category :-) – David Roberts Oct 17 '13 at 0:25
• @David: It depends what you want to do. In the 2-category and bi-category approaches, the objects on the groupoid side are actual groupoids while the objects on the orbifold side are pairs consisting of the topological space underlying the orbifold and a choice of an orbifold atlas representing the orbifold structure. In this case, each orbifold gives rise to infinitely many objects. – Maik Köster Oct 17 '13 at 6:39
• This is fine if you are mainly interested in properties of groupoids. However, when you are interested in orbifolds as geometric objects, you need your objects to be proper orbifolds (as you have manifolds as objects in the category of manifolds and not topological spaces and a choice of covering charts). – Maik Köster Oct 17 '13 at 6:45
• However, if you use groupoids as objects on the one side and orbifolds as objects on the other side, the categories are just equivalent not isomorphic. Switching between the categories forgets the information on diffeomorphisms. This is not sufficient if you want to investigate the diffeomorphism group of an orbifold. – Maik Köster Oct 17 '13 at 6:45
• Constructing the 2-category David Roberts mentions is an intermediate step in the construction of the 1-categories which are actually isomorphic (not just equivalent). One should remark that in this 1-category of groupoids, the objects are not the groupoids but rather equivalence classes of groupoids. These groupoids are even more extended to be a pair of a groupoid and a topological space to be able to distinguish orbifolds which are diffeomorphic but not identical. – Maik Köster Oct 17 '13 at 6:49

A groupoid is a category where every morphism is invertible. If such a category has one object, then it is a group. Unfortunately I don't know why people are so interested in them, so perhaps this is not helpful.

An example is the fundamental groupoid of path classes in a topological space; the objects are points and morphisms p->q are homotopy classes of curves from p to q. Composition is defined by placing together two paths so this is not a group.

• Sorry,Josh's post hadn't appeared when I wrote this; it covers pretty much what I said and more. – Akhil Mathew Oct 19 '09 at 1:16
• but he didnt mention your group comment which he should have. so they are groups with many objects. – Sean Tilson Apr 3 '10 at 0:30

Lots of things are groupoids, but many are not groups. There is a theory of groupoids, and if you don't acknowledge groupoids, they won't let you use their theory =)

The fundamental group(oid) example is really good. What happens if you want to do Van Kampen's theorem on a pair of sets whose intersection is not connected? There's an answer but you have to use fundamental groupoids.

Also, categories are sometimes useful for isolating data. For example, you can replace the usual notion of a local system with a "representation of the fundamental groupoid" and doing so lets you think of a local system the way you already wanted to in your heart: as a collection of operators on fibers coming from "going around the bad points".

Here's a stupid riddle for everyone: what's another word for a "monoidoid"?

• Isn't a monoidoid a category? – Mariano Suárez-Álvarez Jan 28 '10 at 5:33
• Yes, and thus a monoidal category is a.... – Pete L. Clark Jan 28 '10 at 5:38
• One-object monoidoidoid? – Qiaochu Yuan Jan 28 '10 at 5:54
• Mariano Suárez-Alvarez is correct! – Sean Rostami Jan 28 '10 at 19:35

As above, a groupoid is an object where every morphism is an isomorphism, and generalizes groups. As for why to get excited about them, they're useful in classification of things. Like, say you want to understand vector bundles on a space. One method of doing so is constructing the "stack" of vector bundles on that space, which, to each open set (actually, a bit more generally, but thinking concretely here rather than going to grothendieck topologies) associates the groupoid consisting of vector bundles on that open set along with isomorphisms, so that the set of vector bundles is the set of isomorphism classes in this groupoid. The stack made up this way has the property that any family of bundles (or whatever, groupoids work for many things) over some space T is equivalent to giving a morphism from T to the stack.

I also unfortunately don't really understand why people care so much about them, although I should probably go back and read old TWFs.

Sort of a combinatorial example of the fundamental groupoid is the category assigned to a graph where the objects are vertices and the morphisms are directed paths, and v->w->v = id_v. (If this makes sense.) I believe that this category is nice because (IIRC) you can read off the definition of graph homomorphism from it.

ETA: Okay, a quick Baez-review gives the following, which isn't strictly speaking what you asked about but which helps me understand how groupoids are intrinsically special and not just occasionally an improvement that encodes more data than groups.

If you move from categories to n-categories, you can define n-groupoids, although this is subtle. Now, just as the fundamental groupoid is a more natural construction than the fundamental group, n-groupoids capture more information about homotopy than do "monoidal n-groupoids." But furthermore, all the constructions of homotopy are in some way reversible (if I'm following Baez correctly) -- not only is homotopy equivalence an equivalence relation, but even on higher levels this is true -- e.g., the fundamental groupoid functor has an adjoint, which is essentially the classifying space construction, so actually n-categories capture everything about homotopy! And in fact, Baez says that if you think about \omega-categories (which are a limit of n-categories, essentially, I guess?) then the homotopy category of \omega-groupoids is equivalent to the homotopy category.

• This brings up something else I'd like to know, namely what is a graph homomorphism? – Emily Peters Oct 19 '09 at 1:15
• A graph homomorphism from G to H is pretty much exactly what it "should" be, categorically -- it's a function from V(G) to V(H) that preserves adjacency. It simultaneously generalizes the notions of subgraph and of graph coloring, which is nice, but it's kind of nasty to work with in practice. – Harrison Brown Oct 19 '09 at 1:29