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. Triangle finding problem. The triangle finding  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 "m" edges is triangle-free in time O("m"). Another approach is to find the trace of "A", 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 relies on matrix  multiplication, since it gets the time complexity down to O("n"), where "n" is the number of vertices. As showed, triangle-free graph recognition is equivalent in complexity to median graph recognition; however, the current best algorithms for median graph recognition use triangle detection as a subroutine rather than vice versa. The decision tree complexity or query complexity of the problem, where the queries are to an oracle which stores the adjacency matrix of a graph, is Θ("n"). However, for quantum algorithms, the best known lower bound is Ω("n"), but the best known algorithm is O("n"). Independence number and Ramsey theory . An independent set of √"n" vertices in an "n"-vertex triangle-free graph is easy to find: either there is a vertex with more than √"n" neighbors (in which case those neighbors are an independent set) or all vertices have less than √"n" neighbors (in which case any maximal independent set must have at least √"n" vertices). This bound can be tightened slightly: in every triangle-free graph there exists an independent set of formula_1 vertices, and in some triangle-free graphs every independent set has formula_2 vertices. One way to generate triangle-free graphs in which all independent sets are  small is the "triangle-free process" in which one generates a maximal triangle-free graph by repeatedly adding randomly chosen edges that do not complete a triangle. With high probability, this process produces a graph with independence number formula_2. It is also possible to find regular graphs with the same properties. These results may also be interpreted as giving asymptotic bounds on the Ramsey numbers R(3,"t") of the form formula_4: if the edges of a complete graph on formula_5 vertices are colored red and blue, then either the red graph contains a triangle or, if it is triangle-free, then  it must have an independent set of size "t" corresponding to a clique of the same size in the blue graph. Coloring triangle-free graphs. Much research about triangle-free graphs has focused on graph coloring. Every bipartite graph (that is, every 2-colorable graph) is triangle-free, and Grötzsch's theorem states that every triangle-free planar graph may be 3-colored. However, nonplanar triangle-free graphs may require many more than three colors. The first construction of triangle free graphs with arbitrarily high chromatic number is due to Tutte (writing as Blanche Descartes). This construction started from the  graph with a single vertex say formula_6 and inductively constructed formula_7 from formula_8 as follows: let formula_8 have formula_10 vertices, then take a set formula_11 of formula_12 vertices and for each subset formula_13 of formula_11 of size formula_10 add a disjoint copy of formula_8 and join it to formula_13 with a matching. From the pigeonhole principle it follows inductively that formula_7 is not formula_19 colourable, since at least one of the sets formula_13 must be coloured monochromatically if we are only allowed to use k colours. defined a construction, now called the Mycielskian, for forming a new triangle-free graph  from another triangle-free graph. If a graph has chromatic number "k", its Mycielskian has chromatic number "k" + 1, so this construction may be used to show that arbitrarily large numbers of colors may be needed to color nonplanar triangle-free graphs. In particular the Grötzsch graph, an 11-vertex graph formed by repeated application of Mycielski's construction, is a triangle-free graph that cannot be colored with fewer than four colors, and is the smallest graph with this property. and showed that the number of colors needed to color any "m"-edge triangle-free graph is and  that there exist triangle-free graphs that have chromatic numbers proportional to this bound. There have also been several results relating coloring to minimum degree in triangle-free graphs. proved that any "n"-vertex triangle-free graph in which each vertex has more than 2"n"/5 neighbors must be bipartite. This is the best possible result of this type, as the 5-cycle requires three colors but has exactly 2"n"/5 neighbors per vertex. Motivated by this result, conjectured that any "n"-vertex triangle-free graph in which each vertex has at least "n"/3 neighbors can be colored with only three colors; however, disproved  this conjecture by finding a counterexample in which each vertex of the Grötzsch graph is replaced by an independent set of a carefully chosen size. showed that any "n"-vertex triangle-free graph in which each vertex has more than 10"n"/29 neighbors must be 3-colorable; this is the best possible result of this type, because Häggkvist's graph requires four colors and has exactly 10"n"/29 neighbors per vertex. Finally, proved that any "n"-vertex triangle-free graph in which each vertex has more than "n"/3 neighbors must be 4-colorable. Additional results of this type are not possible, as Hajnal found  examples of triangle-free graphs with arbitrarily large chromatic number and minimum degree (1/3 − ε)"n" for any ε > 0.