Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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

Seeing as graphs model relations and algebra is essentially entirely based on relations, one would think that the two fields would inform each other. I know that algebra has many applications to graph theory, but what about applications of graph theory in algebra? Lattice theory, category theory, whatever.

share|cite|improve this question
Cayley graphs are apparently objects of interest in group theory. However, I have no further information to give on this front, as I have myself been fruitless in my efforts to find out why. – A.Sh Feb 18 at 11:40

The Amitsur Levitzki theorem can be proven using Euler trails. There's a statement of the theorem and a proof in my blog.

share|cite|improve this answer

Based on nothing more than a vague knowledge of these subjects' existence and the power of Wikipedia, I came up with two. Since these aren't topics I've studied much, I can't say for sure how much actual graph theory is involved. But I can vouch for the fact that graphs seem to be commonly used tools, at the very least for advertising the field to grad students.

Geometric Group Theory

Another important idea in geometric group theory is to consider finitely generated groups themselves as geometric objects. This is usually done by studying the Cayley graphs [...] endowed with the structure of a metric space, given by the so-called word metric.

Bass-Serre Theory

The theory relates group actions on trees with decomposing groups as iterated applications of [algebra things], via the notion of the fundamental group of a graph of groups.

share|cite|improve this answer

Let $G$ be a group and $H$ be a finite index subgroup of $G$. Say $|G:H|=n$. There there exists elements $g_1, \ldots, g_n\in G$ such that the set $\{g_1, \ldots, g_n\}$ forms a set of representatives of all the left cosets of $H$ in $G$ as well as the set of all the right cosets of $H$ in $G$ simultaneously.

This fact has an algebraic proof but it can be neatly proved using the Hall's Matching Theorem (a.k.a the marriage theorem).

share|cite|improve this answer
$H$ can be either a finite indes subgroup or a finite subgroup of $G.$ – bof Feb 18 at 7:41
@bof I didn't know that the result is true for finite subgroups too. Can you please outline proof? – caffeinemachine Feb 18 at 7:47
Instead of trying to cram a proof outline into a comment, I give a reference: Theorem 10.1.6 on p. 171 of L. Mirsky, Transversal Theory, Academic Press, 1971. "Let $H$ be a finite subgroup of an arbitrary group $G.$ Then the family of left cosets of $H$ and that of right cosets of $H$ possess a common transversal." – bof Feb 18 at 8:07
@bof I have a truly marvelous demonstration of this proposition which this margin is too narrow to contain. Fixed that for you! :P – stackErr Feb 18 at 16:47

Some methods for solving huge sparse system of linear equations use some graph theory.

Try searching the Internet for "system of linear equations" and "strong connected component". The idea is to break the task into smaller (if possible) before applying traditional algebraic methods.

This article seems to be the best introduction.

share|cite|improve this answer

In the theory of permutation groups, there is a result that says that a finite primitive group that contains a transposition is the symmetric group. The proof uses Higman's theorem that if the permutation group is primitive, then a particular orbital digraph is connected.

share|cite|improve this answer

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.