Some facts are-
Group can be represented by a graph.
Group Isomorphism $\leq_p$ Graph Isomorphism.
Under this context, my questions is-
- 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.
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.