Triangle-free graph

In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with girth ≥ 4, graphs with no induced 3-cycle, or locally independent graphs. By Turán's theorem, the n-vertex triangle-free graph with the maximum number of edges is a complete bipartite graph in which the numbers of vertices on each side of the bipartition are as equal as possible. The triangle finding or triangle detection problem is the problem of determining whether a graph is triangle-free or not. When the graph does contain a triangle, algorithms are often required to output three vertices which form a triangle in the graph. It is possible to test whether a graph with edges is triangle-free in time where the hides sub-polynomial factors and is the exponent of fast matrix multiplication. it is known that from which it follows that triangle detection can be solved in time . Another approach is to find the trace of A^3, where A is the adjacency matrix of the graph. The trace is zero if and only if the graph is triangle-free. For dense graphs, it is more efficient to use this simple algorithm which again relies on matrix multiplication, since it gets the time complexity down to , where is the number of vertices. Even if matrix multiplication algorithms with time were discovered, the best time bounds that could be hoped for from these approaches are or . In fine-grained complexity, the sparse triangle hypothesis is an unproven computational hardness assumption asserting that no time bound of the form is possible, for any , regardness of what algorithmic techniques are used. It, and the corresponding dense triangle hypothesis that no time bound of the form is possible, imply lower bounds for several other computational problems in combinatorial optimization and computational geometry.