Hubbry Logo
Triangle-free graphTriangle-free graphMain
Open search
Triangle-free graph
Community hub
Triangle-free graph
logo
8 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Triangle-free graph
Triangle-free graph
Triangle-free graph
View on Wikipedia
from Wikipedia

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.

The triangle-free graphs with the most edges for their vertices are balanced complete bipartite graphs. Many triangle-free graphs are not bipartite, for example any cycle graph Cn for odd n > 3.

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

[edit]

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;[1] from which it follows that triangle detection can be solved in time . Another approach is to find the trace of A3, 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.[2]

As Imrich, Klavžar & Mulder (1999) 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 Θ(n2). However, for quantum algorithms, the best known lower bound is Ω(n), but the best known algorithm is O(n5/4).[3]

Independence number and Ramsey theory

[edit]

An independent set of vertices (where is the floor function) 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).[4] 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.[5] One way to generate triangle-free graphs in which all independent sets are small is the triangle-free process[6] 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 graphs with the same properties.[7]

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

[edit]
The Grötzsch graph is a triangle-free graph that cannot be colored with fewer than four colors

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.[8] 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[9]). 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 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. Mycielski (1955) 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.[10] Gimbel & Thomassen (2000) and Nilli (2000) 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. Andrásfai, Erdős & Sós (1974) proved that any n-vertex triangle-free graph in which each vertex has more than 2n/5 neighbors must be bipartite. This is the best possible result of this type, as the 5-cycle requires three colors but has exactly 2n/5 neighbors per vertex. Motivated by this result, Erdős & Simonovits (1973) 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, Häggkvist (1981) 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. Jin (1995) showed that any n-vertex triangle-free graph in which each vertex has more than 10n/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 10n/29 neighbors per vertex. Finally, Brandt & Thomassé (2006) 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[11] found examples of triangle-free graphs with arbitrarily large chromatic number and minimum degree (1/3 − ε)n for any ε > 0.

See also

[edit]
  • 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 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

[edit]
[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Triangle-free graph

View on Grokipedia
from Grokipedia
A triangle-free graph is a simple undirected graph that contains no cycles of length three, meaning it has no three vertices that are all pairwise adjacent. This property distinguishes triangle-free graphs from more general graphs and makes them a fundamental object of study in and combinatorial . One of the most notable results concerning triangle-free graphs is Mantel's theorem, which determines the maximum possible number of edges in an n-vertex triangle-free graph as ⌊n2/4⌋\lfloor n^2/4 \rfloor. This extremal number is achieved uniquely by the complete bipartite graph K⌊n/2⌋,⌈n/2⌉K_{\lfloor n/2 \rfloor, \lceil n/2 \rceil}, which is balanced and triangle-free by construction. Mantel's theorem, proved in 1907, serves as the foundational case of for forbidding the complete graph K3K_3. Triangle-free graphs also exhibit intriguing chromatic properties: while bipartite graphs (a subclass of triangle-free graphs) are 2-colorable, there exist triangle-free graphs with arbitrarily high chromatic numbers. The Mycielski construction provides an explicit method to generate such graphs, iteratively building a sequence of triangle-free graphs MkM_k where the chromatic number is exactly k for any integer k ≥ 2. For example, the Grötzsch graph, obtained via this construction for k=4, is the smallest triangle-free graph with chromatic number 4. Beyond extremal and coloring aspects, nearly all random triangle-free graphs are bipartite, with the non-bipartite exceptions requiring only the removal of a single vertex to become bipartite. These properties highlight the structural richness of triangle-free graphs, influencing applications in network design, coding theory, and computational complexity.

Fundamentals

Definition

In graph theory, a triangle-free graph is a simple undirected graph G=(V,E)G = (V, E) that contains no subgraph isomorphic to the complete graph K3K_3 on three vertices, meaning there do not exist three distinct vertices u,v,w∈Vu, v, w \in V such that the edges {u,v},{v,w},{w,u}\{u, v\}, \{v, w\}, \{w, u\} are all present in EE. This condition assumes familiarity with basic concepts such as vertices, edges, and induced or isomorphic subgraphs in simple graphs without loops or multiple edges. Equivalently, a graph is triangle-free if it contains no cycles of length three. For a simple undirected graph, this can also be characterized algebraically: if AA is the of GG, then the trace of A3A^3 is zero, since (A3)ii(A^3)_{ii} counts the number of closed walks of length three starting and ending at vertex ii, and such walks correspond to triangles when normalized appropriately. The notion of triangle-free graphs originated in , where Willem Mantel in proved a foundational result bounding the maximum number of edges in such graphs on nn vertices. Mantel's work introduced the core concept by studying graphs without triangles. All bipartite graphs form an important subclass of triangle-free graphs, as they admit no odd-length cycles.

Basic Properties

A triangle-free graph has no cycles of length 3, which implies that its girth is at least 4 if the graph contains any cycles. This property distinguishes triangle-free graphs from those with smaller girth, ensuring that all cycles, when present, are of length 4 or greater. Triangle-free graphs are precisely those without an induced subgraph isomorphic to the K3K_3. While they forbid K3K_3, they permit induced odd cycles of length 5 or more, such as C5C_5. Regarding broader graph classes, triangle-free graphs are not necessarily chordal, as chordal graphs require every cycle of length at least 4 to have a chord, a condition violated by induced cycles longer than 3. In the context of , the strong perfect graph theorem states that a graph is if and only if it contains neither an induced odd cycle of length at least 5 (odd hole) nor its complement (odd antihole); thus, any triangle-free lacks odd holes and must be bipartite. With respect to degree conditions, a triangle-free graph on nn vertices cannot have a vertex of degree n−1n-1 unless it is bipartite, since the neighbors of such a vertex would form an independent set, partitioning the graph into two color classes. More generally, Mantel's theorem establishes that the maximum number of edges in an nn-vertex triangle-free graph is ⌊n2/4⌋\lfloor n^2/4 \rfloor, implying an average degree of at most n/2n/2. Combinatorially, the absence of triangles means that no two adjacent vertices share a common neighbor. In terms of the adjacency matrix AA, this is equivalent to Aij2=0A^2_{ij} = 0 whenever Aij=1A_{ij} = 1 (for i≠ji \neq j), emphasizing the structural avoidance of paths of length 2 between adjacent vertices. Equivalently, the trace of A3A^3 is zero, as tr⁡(A3)/6\operatorname{tr}(A^3)/6 counts the number of triangles.

Examples and Constructions

Bipartite Graphs

Bipartite graphs constitute the canonical class of triangle-free graphs, as they inherently lack any odd-length cycles, including triangles. A is defined as a graph whose vertex set can be partitioned into two disjoint independent sets such that every edge connects a vertex from one set to a vertex in the other. This structure ensures that no three vertices can form a cycle of length 3, since such a cycle would require an odd number of edges alternating between the two sets, which is impossible. A fundamental characterization states that a graph is bipartite if and only if it contains no odd cycles. Consequently, the absence of odd cycles is a stronger property than mere triangle-freeness, as it excludes all odd-length cycles beyond length 3. Bipartite graphs are also precisely the 2-colorable graphs, where vertices can be colored with two colors such that no adjacent vertices share the same color, reflecting their partition into independent sets. Among triangle-free graphs, complete bipartite graphs Km,nK_{m,n} serve as key extremal constructions for maximizing the number of edges while avoiding triangles. In a Km,nK_{m,n}, every vertex in one part of size mm connects to every vertex in the other part of size nn, yielding m⋅nm \cdot n edges with no edges within parts. The balanced case, where the parts are as equal as possible, optimizes this for a fixed number of vertices. Specifically, the Turán graph T(n,2)T(n,2), which is the complete bipartite graph K⌊n/2⌋,⌈n/2⌉K_{\lfloor n/2 \rfloor, \lceil n/2 \rceil}, achieves the maximum of ⌊n2/4⌋\lfloor n^2/4 \rfloor edges in an nn-vertex triangle-free graph. This construction underlies the proof of Mantel's theorem, demonstrating that the extremal triangle-free graph is bipartite.

Non-Bipartite Examples

The C5C_5, consisting of five vertices connected in a single cycle, is the smallest non-bipartite triangle-free graph, as its girth of 5 ensures no triangles while the odd length prevents bipartiteness. The , a 3-regular graph on 10 vertices with 15 edges, exemplifies a symmetric non-bipartite triangle-free graph with girth 5, making it the unique (3,5)-cage graph. Originally described by Julius Petersen in 1898 as a in , it features no cycles shorter than 5 and serves as a foundational example in due to its high symmetry and minimal size for these properties. Mycielski graphs provide a recursive construction of non-bipartite triangle-free graphs with arbitrarily high chromatic numbers, starting from simpler graphs like the cycle C5C_5 and iteratively adding vertices to increase the chromatic number by 1 while preserving triangle-freeness. A prominent example is the Grötzsch graph, the Mycielski graph of order 4 with 11 vertices and 20 edges, which is the smallest known triangle-free graph with chromatic number 4. The Clebsch graph, a strongly regular graph on 16 vertices with parameters (16,5,0,2), is another non-bipartite triangle-free example where the parameter λ=0\lambda = 0 explicitly ensures no triangles, while its 5-regular structure and girth of 4 highlight properties in association schemes.

Extremal Graph Theory

Mantel's Theorem

Mantel's theorem is a foundational result in extremal graph theory, stating that the maximum number of edges in a triangle-free graph on nn vertices is ⌊n2/4⌋\lfloor n^2 / 4 \rfloor. This bound is achieved uniquely by the complete bipartite graph K⌊n/2⌋,⌈n/2⌉K_{\lfloor n/2 \rfloor, \lceil n/2 \rceil}, which partitions the vertices into two nearly equal sets and includes all possible edges between them. The theorem was proved by Willem Mantel in 1907 as a solution to a problem posed in the Dutch journal Wiskundige Opgaven. Mantel's result marks the origin of and serves as the special case r=2r=2 of , which generalizes the bound to graphs avoiding complete subgraphs Kr+1K_{r+1}. A standard proof proceeds by double-counting the sum of degrees over the edges. Let G=(V,E)G = (V, E) be a triangle-free graph with ∣V∣=n|V| = n and ∣E∣=m|E| = m. Since GG has no triangles, any two adjacent vertices xx and yy share no common neighbors, so deg⁡(x)+deg⁡(y)≤n\deg(x) + \deg(y) \leq n. Summing over all edges gives ∑xy∈E(deg⁡(x)+deg⁡(y))≤mn\sum_{xy \in E} (\deg(x) + \deg(y)) \leq m n. The left side equals ∑x∈Vdeg⁡(x)2\sum_{x \in V} \deg(x)^2, and by the , ∑x∈Vdeg⁡(x)=2m\sum_{x \in V} \deg(x) = 2m. Applying the Cauchy-Schwarz inequality yields ∑x∈Vdeg⁡(x)2≥(2m)2n\sum_{x \in V} \deg(x)^2 \geq \frac{(2m)^2}{n}, so (2m)2n≤mn\frac{(2m)^2}{n} \leq m n, implying m≤n2/4m \leq n^2 / 4. Thus, m≤⌊n2/4⌋m \leq \lfloor n^2 / 4 \rfloor. Equality holds when GG is the balanced , as all degrees are equal and the inequality becomes tight. An alternative proof considers a vertex vv of maximum degree dd. The neighbors of vv form an independent set (no edges among them, due to triangle-freeness), so the edges incident to vv number dd, and the remaining edges are at most those in the on the n−d−1n - d - 1 non-neighbors plus edges from non-neighbors to neighbors (at most (n−d)(d)(n - d)(d), but refined analysis shows the maximum occurs at d=n/2d = n/2). This degree-based argument confirms the same bound.

Zarankiewicz Problem

The Zarankiewicz problem seeks to determine the maximum number of edges in a bipartite graph with bipartition sizes mm and nn that contains no complete bipartite subgraph Ks,tK_{s,t}, where the maximum is denoted by z(m,n;s,t)z(m,n;s,t). This extremal function quantifies the densest possible bipartite graphs avoiding a fixed forbidden complete bipartite minor, serving as a bipartite counterpart to classical Turán-type problems in graph theory. In the context of triangle-free graphs, the problem is particularly relevant because all bipartite graphs are triangle-free by definition, allowing the Zarankiewicz bounds to establish upper limits on edge counts in triangle-free graphs that additionally avoid denser bipartite configurations. A foundational result is the Kővári–Sós–Turán theorem, which states that z(m,n;s,t)≤(s−1)1/t n m1−1/t+(t−1)m.z(m,n;s,t) \leq (s-1)^{1/t} \, n \, m^{1 - 1/t} + (t-1) m. This upper bound is asymptotically tight in many cases and provides a general framework for estimating extremal densities. For the specific case s=t=2s = t = 2, which corresponds to C4C_4-free bipartite graphs (since K2,2K_{2,2} is a 4-cycle), the theorem yields z(m,n;2,2)≤nm1/2+mz(m,n;2,2) \leq n m^{1/2} + m, highlighting subquadratic growth in the number of edges relative to the Km,nK_{m,n}. Constructions achieving near-optimality, such as incidence graphs of finite geometries, often meet this bound up to constant factors. The Zarankiewicz problem ties directly to triangle-free graphs by bounding substructures within bipartite extremal examples; for instance, in balanced bipartitions, avoiding K2,2K_{2,2} aligns with constraints beyond those of Mantel's theorem, which maximizes edges without triangles in general graphs. Advances have refined asymptotic bounds, particularly for forbidding even cycles C2ℓC_{2\ell} in bipartite graphs, with further progress as of 2025 including tight bounds towards the Zarankiewicz problem in hypergraphs. For ℓ∈{2,3,5}\ell \in \{2, 3, 5\} and sufficiently large odd cycle lengths, the extremal number ex(n,C2ℓ∪{Ck})\mathrm{ex}(n, C_{2\ell} \cup \{C_k\}) matches the Zarankiewicz density z(n,C2ℓ)z(n, C_{2\ell}) asymptotically, resolving cases of the and confirming bipartite incidence graphs of generalized polygons as extremal.

Algorithms and Detection

Triangle Detection Algorithms

Triangle detection algorithms aim to determine whether a graph contains a , which is crucial for verifying triangle-freeness in various applications, including network analysis and . The simplest approach is the naive algorithm, which enumerates all possible triples of vertices and checks if each triple forms a complete subgraph K3K_3 by verifying the presence of edges between all three pairs. This method has a of O(n3)O(n^3), where nn is the number of vertices, making it straightforward but inefficient for large graphs. Theoretical advancements leverage algebraic techniques for faster detection. A prominent method reduces triangle detection to matrix multiplication: given the adjacency matrix AA of the graph, computing A3A^3 and checking its diagonal entries (or the trace for counting) identifies triangles, as the (i,i)(i,i)-entry of A3A^3 counts walks of length 3 from ii to itself, including triangles. Using fast matrix multiplication algorithms, such as those achieving an exponent ω≤2.371339\omega \leq 2.371339, this yields a detection time of O(nω)O(n^\omega). This equivalence between triangle detection and Boolean matrix multiplication has been established as a foundational result in fine-grained complexity. The fastest known algorithms achieve O(nω)O(n^\omega) time using fast matrix multiplication. It remains an open problem whether a combinatorial algorithm running in O(n3−ϵ)O(n^{3-\epsilon}) time for some ϵ>0\epsilon > 0 exists. For sparse graphs with mm edges, where m=o(n2)m = o(n^2), combinatorial algorithms exploiting provide practical speedups. The Itai-Rodeh iterates over edges and checks for common neighbors, achieving O(m3/2)O(m^{3/2}) time by bounding the degree-based searches. This is particularly effective when graphs have low density, as it avoids the cubic overhead of dense methods. In practice, algorithms like the node-iterator and edge-iterator are widely used for large-scale triangle detection. The node-iterator processes each vertex, intersecting the neighborhoods of its adjacent vertices to find common neighbors forming triangles, with O(∑vdv2)O(\sum_v d_v^2), where dvd_v is the degree of vv. The edge-iterator, conversely, directs edges from lower- to higher-degree vertices and checks intersections along each edge, often performing better on real-world networks due to reduced redundant computations; both are implemented in libraries like SNAP and GraphBLAS for efficient execution on massive datasets. Quantum algorithms offer theoretical speedups over classical methods, though they remain primarily of academic interest. Using Grover's search framework, algorithms can detect triangles in O(n1.3)O(n^{1.3}) quantum queries by searching over potential triples or edges while amplifying promising paths, as developed in early quantum graph algorithm research. More recent quantum algorithms improve this to O~(n5/4)\tilde{O}(n^{5/4}) time. However, classical algorithms dominate practical implementations due to current hardware limitations.

Complexity Results

The computational complexity of detecting triangles in general graphs has been extensively studied in fine-grained complexity theory. The fastest known algorithms for triangle detection run in O(nω)O(n^\omega) time, where ω≤2.371339\omega \leq 2.371339 is the exponent of square matrix multiplication, achieved by reducing the problem to fast matrix multiplication over the Boolean semiring. No truly subcubic O(n3−ϵ)O(n^{3-\epsilon}) time combinatorial algorithm exists, as triangle detection is combinatorially equivalent to Boolean matrix multiplication up to polylogarithmic factors. Conditional lower bounds based on the 3SUM conjecture further suggest that no O(n4/3poly(log⁡n))O(n^{4/3} \mathrm{poly}(\log n)) time algorithm exists for sparse graphs. Counting the number of triangles in a graph is #P-complete, as it corresponds to counting homomorphisms from the input graph to the K3K_3, which falls outside the polynomial-time tractable cases identified in the dichotomy theorem for counting. Despite this hardness, exact triangle counting is fixed-parameter tractable when parameterized by the of the graph, via dynamic programming on tree decompositions that counts subgraphs in O(4twn)O(4^{tw} n) time, where twtw is the . It is also fixed-parameter tractable parameterized by the degeneracy of the graph, leveraging the fact that degenerate graphs admit efficient of small subgraphs. Enumerating all triangle-free graphs on nn vertices up to can be performed without duplicates using generation techniques, which build graphs vertex-by-vertex while enforcing a construction path to avoid isomorphic copies. This approach, implemented using tools like nauty for computations, achieves amortized time per generated graph, with practical generation rates exceeding 20,000 graphs per second on modest hardware for moderate nn. The total number of such graphs grows as 2Θ(n2/4)2^{\Theta(n^2 / 4)} by Mantel's , making exhaustive enumeration feasible only for small nn despite the efficient per-object time.

Structural Bounds

Independence Number

In triangle-free graphs, the independence number α(G)\alpha(G) for a graph GG on nn vertices satisfies α(G)≥cnlog⁡dd\alpha(G) \geq c \frac{n \log d}{d} for average degree d≥1d \geq 1 and some absolute constant c>0c > 0. This seminal bound, due to Ajtai, Komlós, and Szemerédi, provides a direct lower bound that improves upon simpler estimates when dd is moderate, and it arises from probabilistic constructions identifying large independent sets via conditional expectations on random subsets. A cruder but elementary guarantee follows from the relation to the clique number ω(G)=2\omega(G) = 2, yielding α(G)≥nχ(G)\alpha(G) \geq \frac{n}{\chi(G)} via the standard inequality α(G)χ(G)≥n\alpha(G) \chi(G) \geq n, though direct methods like the above emphasize independence without relying on coloring complexity. For algorithmic purposes, a greedy approach to approximating α(G)\alpha(G) can leverage coloring: applying in an arbitrary order produces at most Δ(G)+1\Delta(G) + 1 colors, where the largest color class forms an independent set of size at least nΔ(G)+1\frac{n}{\Delta(G) + 1}; in graphs achieving the minimal possible α(G)≈nlog⁡n\alpha(G) \approx \sqrt{n \log n}
Add your contribution
Related Hubs
User Avatar
No comments yet.