# Graph where edges have group structure

In the mathematical literature there are examples of graphs where the vertices form a group - the most famous example are probably the Cayley graphs.

I'm curious about a somewhat dual situation. Are there examples in mathematics of multigraphs (many possible edges between the same two vertices), where the set of edges between two vertices forms a group in an interesting way?

I'd be particularly interested in the case of an abelian group, that could be interpreted as "the sum of two edges is again an edge".

• It sounds like you might be thinking about the concept of a group action. In a Cayley graph, while it may be true that there is a bijection between group elements and vertices, I think it is an over-interpretation to state this as "the vertices form a group". A much more useful interpretation -- in fact, a theorem -- is that the group acts on its Cayley graph, and the action restricted to the vertex set is transitive and free. Feb 9, 2022 at 13:52
• And, by the way, if you are not too careful about your terminology then in some sense any set forms a group. Feb 9, 2022 at 13:56
• @LeeMosher That is an interesting idea. Are there examples of multigraphs where the sets of edges between two vertices all admit actions of the same group (in an interesting way)? Feb 9, 2022 at 15:01

## 1 Answer

While this is well outside my area and so I wouldn't be fully comfortable to say "no", I think this extended comment may be of some interest.

The idea of attaching group elements to vertices is "in the spirit" of other mathematical ideas, in a way that's harder to interpret for edges. The Cayley graph originates in geometric group theory, which aims to study a group by considering spaces on which the group acts. The rough* idea of the Cayley graph is to turn the group itself into a space, since it already has an action. Well, at minimum, such a space must have group elements as its points! And it is reasonable to think about vertices of a graph as points of a space.

When you flip it around and ask "What are the edges of a graph doing?" the answer is that they are describing the existence of "a relationship" between two vertices. For the Cayley graph this means that two vertices differ by a generator, but of course there are all sorts of other relationships that may be possible.

Critically, though: note that this answer is really about the set of edges between two vertices. The set of edges is much less coherent as a "uniform" collection. There is a reason that when a group is represented as a category, then yes the group elements become edges (arrows), but there is only one vertex (object)!** Doing this "uniformizes" the edge set by forcing all edges to have the same endpoints.

The way I see it, what a group really "wants" to do as a collection of edges is not to uniquely label every edge of a graph, but rather to label the collection of edges that originate at a particular vertex. After all, the whole point of a group is to act on something (usually by symmetries); so it is natural to ask what the action does. This gives rise immediately to a graph structure (with edges $$x\to gx$$), and edges are labelled by group elements, but of course if there is more than one vertex then each element appears many times.

(* "Rough" in the sense that literally speaking, this is at odds with Lee Mosher's interpretation, and theirs is better. The distinction that Mosher is making is important: if you start with a graph that is unlabelled but I tell you it is a Cayley graph $$\Gamma(G,S)$$, you will not be able to find the identity element, even if you know $$G$$ and $$S$$, and even if the edges are already $$S$$-labelled. So we are not literally making $$G$$ into a space, but only making a space that "looks like" $$G$$.)

(** But, you may also be interested in groupoids.... It's not an answer to your question since it really is a cheat; groupoids are more or less defined to be the edge sets of graphs. Well, that's not quite true, but it's not far off.)

• "if you start with a graph that is unlabelled but I tell you it is a Cayley graph, you will not be able to find the identity element", this is a really good point! Feb 9, 2022 at 14:28
• Indeed it is (thanks Mosher!) and I will add that this distinction is precisely what one should think of when hearing the phrase "free transitive action". (And while we're in this circle of ideas: I also feel like I could have saved a lot of trouble if someone had sat me down one day and told me that free and transitive were the group-action analogues of injective and surjective, respectively.) Feb 9, 2022 at 14:35