# Can a triangle free graph represent a Group?

Some facts are-

1. Group can be represented by a graph.

2. Group Isomorphism $\leq_p$ Graph Isomorphism.

Under this context, my questions is-

1. Can a triangle free graph represent a group?

Edit: My motivation is to see the interaction between group isomorphism and graph isomorphism,so please consider groups that can be represented by simple graphs but not trees as tree isomorphism can be solved in log time.

In general, consider hard instances of groups for group isomorphism which are represented by graphs that are also hard graph isomorphism instances.

• When you say "groups can be represented by a graph" do you mean the Cayley graph ? – Captain Lama Apr 27 '16 at 16:46
• @CaptainLama yes, caley graphs are directed but even if you don't keep the direction of caley graph , they still represent a group. – Jim Apr 27 '16 at 16:55
• Then free groups are "represented" by trees. – Captain Lama Apr 27 '16 at 16:56
• Like... the Cayley graph for a cyclic group with $n \neq 3$ elements? – pjs36 Apr 27 '16 at 17:21
• At any rate, if you just wants lots of examples of (gorgeous) Cayley graphs, check out weddslist. You can spot a few different Cayley graphs for a variety of groups. – pjs36 Apr 27 '16 at 17:27

The thing is that the Cayley graph is not canonical : for a given group $G$, each choice of a generating set will give a different Cayley graph.
And every group with at least $3$ elements has a Cayley graph with triangles : if $x\neq y$ in $G$, put $x$, $y$ and $xy^{-1}$ in the generating set, and this will give you a triangle in the Cayley graph.
On the other hand, unless your generating set has elements of order $3$, you can always remove the triangles by changing the generating set. Indeed, if there is a triangle, then by homogeneity you canfind one with one of the vertices labeled by the neutral element. Then (assuming the generating set $S$ is symmetric) the other two vertices are labeled with $x,y\in S$ and the edges are labeled with $x$, $y$ and $z\in S$. The fact that it's a triangle then means that $z=yx^{-1}$ or $z=yx^{-1}$. Then analysing all cases ($z=x^{\pm 1}$, $z=y^{\pm 1}$, $z\neq x^{\pm 1},y^{\pm 1}$) shows that you can remove one of those generators, thus removing the triangle.
• I think your last statement is correct, but it is not obvious and a proof requires some work. For example, it is not true if you replace $3$ by $4$. If you take an abelian group of rank at least 2, then, for any generating set, the corresponding Cayley graph will have $4$-cycles, (even if the group has no element of order $4$). – verret Apr 27 '16 at 20:02
• That proof is incorrect. For example, on the surface, that proofs work for 4 as well, but the conclusion is wrong in this case. The problem is that the 3- or 4-cycle might have repeated elements. In your notation, we might have $x=z$ so that removing $z$ removes $x$ and we might no longer have a generating set. In the 3-cycle case, that can actually be avoided, with some care... – verret Apr 27 '16 at 20:22
• Yes, you can always find a Cayley graph with triangles for your group if it has at least $3$ elements. – Captain Lama May 18 '16 at 21:39