1. ## Triangle-free graph algorithm

Anybody know how to write an algorithm for testing whether a graph is triangle-free?

2. Originally Posted by moi
Anybody know how to write an algorithm for testing whether a graph is triangle-free?
Here is a thought:

Write an algorithm to go through every vertex (ie depth first search)

At each vertex, check if it is part of a triangle.

To check whether a vertex is part of a triangle, place every vertex it is adjacent to in set A. For every vertex in set A, create a set of every vertex they are adjacent to B_(A_1), B_(A_2), ..., B_(A_n).

If there is any intersection between A and B_(A_1), or A and B_(A_2), or ..., or A and B_(A_n), then the node being tested is part of a triangle. Therefore there is a triangle in the graph.

If you go through your search, and this situation never occurs, then there are no triangles in the graph.

There is probably a better way, but this is the first thing that came to mind.

I attached a picture to show. The green/blue (though you can barely see the blue) vertex is the node being tested, the red vertices are the vertices that it connects to (set A), the blue vertices are the vertices that are in subset B_(A_k) (the set of vertices which vertex A_k is adjacent to). Notice that the vertex which is half red and half blue is in both set A and set B_(A_k), therefore there is a triangle.