In the
mathematical
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
area of
graph theory
In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
, a triangle-free graph is an undirected graph in which no three vertices form a
triangle
A triangle is a polygon with three corners and three sides, one of the basic shapes in geometry. The corners, also called ''vertices'', are zero-dimensional points while the sides connecting them, also called ''edges'', are one-dimension ...
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 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. Here
is the exponent of
fast matrix multiplication;
from which it follows that triangle detection can be solved in time
. Another approach is to find the
trace of , where is the
adjacency matrix
In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph (discrete mathematics), graph. The elements of the matrix (mathematics), matrix indicate whether pairs of Vertex (graph theory), vertices ...
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.
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 . However, for
quantum algorithm
In quantum computing, a quantum algorithm is an algorithm that runs on a realistic model of quantum computation, the most commonly used model being the quantum circuit model of computation. A classical (or non-quantum) algorithm is a finite seq ...
s, the best known lower bound is , but the best known algorithm is .
Independence number and Ramsey theory
An
independent set of
vertices (where
is the
floor function
In mathematics, the floor function is the function that takes as input a real number , and gives as output the greatest integer less than or equal to , denoted or . Similarly, the ceiling function maps to the least integer greater than or eq ...
) in an ''n''-vertex triangle-free graph is easy to find: either there is a vertex with at least
neighbors (in which case those neighbors are an independent set) or all vertices have strictly less than
neighbors (in which case any
maximal independent set must have at least
vertices). This bound can be tightened slightly: in every triangle-free graph there exists an independent set of
vertices, and in some triangle-free graphs every independent set has
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
. It is also possible to find
regular graph
In graph theory, a regular graph is a Graph (discrete mathematics), graph where each Vertex (graph theory), vertex has the same number of neighbors; i.e. every vertex has the same Degree (graph theory), degree or valency. A regular directed graph ...
s with the same properties.
These results may also be interpreted as giving asymptotic bounds on the
Ramsey numbers R(3,''t'') of the form
: if the edges of a complete graph on
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
In graph theory, graph coloring is a methodic assignment of labels traditionally called "colors" to elements of a Graph (discrete mathematics), graph. The assignment is subject to certain constraints, such as that no two adjacent elements have th ...
. Every
bipartite graph
In the mathematics, mathematical field of graph theory, a bipartite graph (or bigraph) is a Graph (discrete mathematics), graph whose vertex (graph theory), vertices can be divided into two disjoint sets, disjoint and Independent set (graph theo ...
(that is, every 2-colorable graph) is triangle-free, and
Grötzsch's theorem states that every triangle-free
planar graph
In graph theory, a planar graph is a graph (discrete mathematics), graph that can be graph embedding, embedded in the plane (geometry), plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. ...
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
and inductively constructed
from
as follows: let
have
vertices, then take a set
of
vertices and for each subset
of
of size
add a disjoint copy of
and join it to
with a matching. From the
pigeonhole principle
In mathematics, the pigeonhole principle states that if items are put into containers, with , then at least one container must contain more than one item. For example, of three gloves, at least two must be right-handed or at least two must be l ...
it follows inductively that
is not
colourable, since at least one of the sets
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
In the mathematical field of graph theory, the Grötzsch graph is a triangle-free graph with 11 vertices, 20 edges, chromatic number 4, and crossing number 5. It is named after German mathematician Herbert Grötzsch, who used it as an example ...
, 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
[see .] found examples of triangle-free graphs with arbitrarily large chromatic number and minimum degree (1/3 − ε)''n'' for any ε > 0.
See also
*
Andrásfai graph, a family of triangle-free circulant graphs with diameter two
*
Henson graph, an infinite triangle-free graph that contains all finite triangle-free graphs as induced subgraphs
*
Shift graph, a family of triangle-free graphs with arbitrarily high chromatic number
*The
Kneser graph is triangle free and has chromatic number
*
Monochromatic triangle
In graph theory and theoretical computer science, the monochromatic triangle problem is an algorithmic problem on graphs,
in which the goal is to partition the edges of a given graph into two triangle-free subgraphs. It is NP-complete but fixe ...
problem, the problem of partitioning the edges of a given graph into two triangle-free graphs
*
Ruzsa–Szemerédi problem, on graphs in which every edge belongs to exactly one triangle
References
Notes
Sources
*
*.
*.
*.
*.
*.
*.
*.
*
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*
*.
*.
*.
*.
*.
*.
*.
*.
External links
* {{Citation , url=http://www.graphclasses.org/classes/gc_371.html , title=Graphclass: triangle-free , work =Information System on Graph Classes and their Inclusions
Graph families