Fact-checked by Grok 2 weeks ago

Triangle-free graph

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.^[1] This property distinguishes triangle-free graphs from more general graphs and makes them a fundamental object of study in extremal graph theory and combinatorial graph theory. 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 \lfloor n^2/4 \rfloor.^[2] This extremal number is achieved uniquely by the complete bipartite graph K_{\lfloor n/2 \rfloor, \lceil n/2 \rceil}, which is balanced and triangle-free by construction.^[2] Mantel's theorem, proved in 1907, serves as the foundational case of Turán's theorem for forbidding the complete graph K_3.^[2] 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.^[3] The Mycielski construction provides an explicit method to generate such graphs, iteratively building a sequence of triangle-free graphs M_k where the chromatic number is exactly k for any integer k ≥ 2.^[4] For example, the Grötzsch graph, obtained via this construction for k=4, is the smallest triangle-free graph with chromatic number 4.^[5] 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) that contains no subgraph isomorphic to the complete graph K_3 on three vertices, meaning there do not exist three distinct vertices u, v, w \in V such that the edges \{u, v\}, \{v, w\}, \{w, u\} are all present in E.^[1] 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.^[1] For a simple undirected graph, this property can also be characterized algebraically: if A is the adjacency matrix of G, then the trace of A^3 is zero, since (A^3)_{ii} counts the number of closed walks of length three starting and ending at vertex i, and such walks correspond to triangles when normalized appropriately.^[1] The notion of triangle-free graphs originated in extremal graph theory, where Willem Mantel in 1907 proved a foundational result bounding the maximum number of edges in such graphs on n vertices.^[6] 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.^[7] This property distinguishes triangle-free graphs from those with smaller girth, ensuring that all cycles, when present, are of length 4 or greater.^[7] Triangle-free graphs are precisely those without an induced subgraph isomorphic to the complete graph K_3.^[8] While they forbid K_3, they permit induced odd cycles of length 5 or more, such as C_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.^[8] In the context of perfect graphs, the strong perfect graph theorem states that a graph is perfect 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 perfect graph lacks odd holes and must be bipartite. With respect to degree conditions, a triangle-free graph on n vertices cannot have a vertex of degree n-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 n-vertex triangle-free graph is \lfloor n^2/4 \rfloor, implying an average degree of at most n/2. Combinatorially, the absence of triangles means that no two adjacent vertices share a common neighbor. In terms of the adjacency matrix A, this is equivalent to A^2_{ij} = 0 whenever A_{ij} = 1 (for i \neq j), emphasizing the structural avoidance of paths of length 2 between adjacent vertices. Equivalently, the trace of A^3 is zero, as \operatorname{tr}(A^3)/6 counts the number of triangles.^[9]

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 bipartite graph 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.^[10] 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.^[11] A fundamental characterization states that a graph is bipartite if and only if it contains no odd cycles.^[12] 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.^[11] Among triangle-free graphs, complete bipartite graphs K_{m,n} serve as key extremal constructions for maximizing the number of edges while avoiding triangles. In a complete bipartite graph K_{m,n}, every vertex in one part of size m connects to every vertex in the other part of size n, yielding m \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), which is the complete bipartite graph K_{\lfloor n/2 \rfloor, \lceil n/2 \rceil}, achieves the maximum of \lfloor n^2/4 \rfloor edges in an n-vertex triangle-free graph.^[13] This construction underlies the proof of Mantel's theorem, demonstrating that the extremal triangle-free graph is bipartite.^[2]

Non-Bipartite Examples

The cycle graph C_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 Petersen graph, 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.^[14] Originally described by Julius Petersen in 1898 as a counterexample in graph factorization, it features no cycles shorter than 5 and serves as a foundational example in extremal graph theory 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 C_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.^[5] 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 \lambda = 0 explicitly ensures no triangles, while its 5-regular structure and girth of 4 highlight properties in association schemes.^[15]^[16]

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 n vertices is \lfloor n^2 / 4 \rfloor.^[17] This bound is achieved uniquely by the complete bipartite graph 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.^[17] The theorem was proved by Willem Mantel in 1907 as a solution to a problem posed in the Dutch journal Wiskundige Opgaven.^[18] Mantel's result marks the origin of extremal graph theory and serves as the special case r=2 of Turán's theorem, which generalizes the bound to graphs avoiding complete subgraphs K_{r+1}.^[17] A standard proof proceeds by double-counting the sum of degrees over the edges. Let G = (V, E) be a triangle-free graph with |V| = n and |E| = m. Since G has no triangles, any two adjacent vertices x and y share no common neighbors, so \deg(x) + \deg(y) \leq n. Summing over all edges gives \sum_{xy \in E} (\deg(x) + \deg(y)) \leq m n. The left side equals \sum_{x \in V} \deg(x)^2, and by the handshaking lemma, \sum_{x \in V} \deg(x) = 2m. Applying the Cauchy-Schwarz inequality yields \sum_{x \in V} \deg(x)^2 \geq \frac{(2m)^2}{n}, so \frac{(2m)^2}{n} \leq m n, implying m \leq n^2 / 4. Thus, m \leq \lfloor n^2 / 4 \rfloor. Equality holds when G is the balanced complete bipartite graph, as all degrees are equal and the inequality becomes tight.^[17] An alternative proof considers a vertex v of maximum degree d. The neighbors of v form an independent set (no edges among them, due to triangle-freeness), so the edges incident to v number d, and the remaining edges are at most those in the induced subgraph on the n - d - 1 non-neighbors plus edges from non-neighbors to neighbors (at most (n - d)(d), but refined analysis shows the maximum occurs at d = n/2). This degree-based argument confirms the same bound.^[2]

Zarankiewicz Problem

The Zarankiewicz problem seeks to determine the maximum number of edges in a bipartite graph with bipartition sizes m and n that contains no complete bipartite subgraph K_{s,t}, where the maximum is denoted by 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) \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 = 2, which corresponds to C_4-free bipartite graphs (since K_{2,2} is a 4-cycle), the theorem yields z(m,n;2,2) \leq n m^{1/2} + m, highlighting subquadratic growth in the number of edges relative to the complete bipartite graph K_{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 K_{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 C_{2\ell} in bipartite graphs, with further progress as of 2025 including tight bounds towards the Zarankiewicz problem in hypergraphs.^[19] For \ell \in \{2, 3, 5\} and sufficiently large odd cycle lengths, the extremal number \mathrm{ex}(n, C_{2\ell} \cup \{C_k\}) matches the Zarankiewicz density z(n, C_{2\ell}) asymptotically, resolving cases of the Erdős–Simonovits conjecture and confirming bipartite incidence graphs of generalized polygons as extremal.^[20]

Algorithms and Detection

Triangle Detection Algorithms

Triangle detection algorithms aim to determine whether a graph contains a triangle, which is crucial for verifying triangle-freeness in various applications, including network analysis and extremal graph theory. The simplest approach is the naive algorithm, which enumerates all possible triples of vertices and checks if each triple forms a complete subgraph K_3 by verifying the presence of edges between all three pairs. This method has a time complexity of O(n^3), where n is the number of vertices, making it straightforward but inefficient for large graphs.^[21] Theoretical advancements leverage algebraic techniques for faster detection. A prominent method reduces triangle detection to matrix multiplication: given the adjacency matrix A of the graph, computing A^3 and checking its diagonal entries (or the trace for counting) identifies triangles, as the (i,i)-entry of A^3 counts walks of length 3 from i to itself, including triangles. Using fast matrix multiplication algorithms, such as those achieving an exponent \omega \leq 2.371339, this yields a detection time of 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^\omega) time using fast matrix multiplication. It remains an open problem whether a combinatorial algorithm running in O(n^{3-\epsilon}) time for some \epsilon > 0 exists.^[22]^[23] For sparse graphs with m edges, where m = o(n^2), combinatorial algorithms exploiting adjacency lists provide practical speedups. The Itai-Rodeh algorithm iterates over edges and checks for common neighbors, achieving 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.^[24] In practice, heuristic 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 time complexity O(\sum_v d_v^2), where d_v is the degree of v. 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.^[25] 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(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 \tilde{O}(n^{5/4}) time. However, classical algorithms dominate practical implementations due to current hardware limitations.^[26]^[27]

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^\omega) time, where \omega \leq 2.371339 is the exponent of square matrix multiplication, achieved by reducing the problem to fast matrix multiplication over the Boolean semiring.^[22] No truly subcubic O(n^{3-\epsilon}) time combinatorial algorithm exists, as triangle detection is combinatorially equivalent to Boolean matrix multiplication up to polylogarithmic factors.^[22] Conditional lower bounds based on the 3SUM conjecture further suggest that no O(n^{4/3} \mathrm{poly}(\log n)) time algorithm exists for sparse graphs.^[28] Counting the number of triangles in a graph is #P-complete, as it corresponds to counting homomorphisms from the input graph to the complete graph K_3, which falls outside the polynomial-time tractable cases identified in the dichotomy theorem for graph homomorphism counting.^[29] Despite this hardness, exact triangle counting is fixed-parameter tractable when parameterized by the treewidth of the graph, via dynamic programming on tree decompositions that counts subgraphs in O(4^{tw} n) time, where tw is the treewidth.^[30] It is also fixed-parameter tractable parameterized by the degeneracy of the graph, leveraging the fact that degenerate graphs admit efficient enumeration of small subgraphs.^[25] Enumerating all triangle-free graphs on n vertices up to isomorphism can be performed without duplicates using orderly generation techniques, which build graphs vertex-by-vertex while enforcing a canonical construction path to avoid isomorphic copies.^[31] This approach, implemented using tools like nauty for automorphism group computations, achieves amortized polynomial time per generated graph, with practical generation rates exceeding 20,000 graphs per second on modest hardware for moderate n.^[31] The total number of such graphs grows as $2^{\Theta(n^2 / 4)} by Mantel's theorem, making exhaustive enumeration feasible only for small n despite the efficient per-object time.^[32]

Structural Bounds

Independence Number

In triangle-free graphs, the independence number \alpha(G) for a graph G on n vertices satisfies \alpha(G) \geq c \frac{n \log d}{d} for average degree d \geq 1 and some absolute constant c > 0. This seminal bound, due to Ajtai, Komlós, and Szemerédi, provides a direct lower bound that improves upon simpler estimates when d is moderate, and it arises from probabilistic constructions identifying large independent sets via conditional expectations on random subsets.^[33] A cruder but elementary guarantee follows from the relation to the clique number \omega(G) = 2, yielding \alpha(G) \geq \frac{n}{\chi(G)} via the standard inequality \alpha(G) \chi(G) \geq n, though direct methods like the above emphasize independence without relying on coloring complexity.^[34] For algorithmic purposes, a greedy approach to approximating \alpha(G) can leverage coloring: applying greedy coloring in an arbitrary order produces at most \Delta(G) + 1 colors, where the largest color class forms an independent set of size at least \frac{n}{\Delta(G) + 1}; in graphs achieving the minimal possible \alpha(G) \approx \sqrt{n \log n}, where \Delta(G) is large (\Theta(n)), this yields an O(\sqrt{n / \log n})-approximation ratio relative to the optimum. Larger guarantees on \alpha(G) connect to Ramsey theory, where off-diagonal bounds imply \alpha(G) \geq c \sqrt{n \log n} for some c > 0, though full details appear in advanced Ramsey contexts. In specific constructions, such as bipartite graphs (a subclass of triangle-free graphs), \alpha(G) equals the size of the larger partite set, which is at least \frac{n}{2}.

Chromatic Number Bounds

The chromatic number \chi(G) of a triangle-free graph G with maximum degree \Delta(G) satisfies \chi(G) \leq \Delta(G) + 1, as implied by Brooks' theorem, since such graphs contain no clique K_3. A tighter asymptotic upper bound, \chi(G) \leq O(\Delta / \log \Delta), was established by Johansson using probabilistic methods involving the Lovász Local Lemma applied iteratively to list colorings. This result improves significantly over the general case for graphs with large \Delta, highlighting the structural sparsity induced by the triangle-free condition. For a dependence on the order n rather than \Delta, since every triangle-free graph G on n vertices has independence number \alpha(G) \geq c \sqrt{n \log n} for some c > 0 by off-diagonal Ramsey bounds, it follows that \chi(G) \leq n / \alpha(G) = O(\sqrt{n / \log n}). Probabilistic methods can achieve this bound in expectation by repeatedly finding and removing large independent sets. On the lower bounds, the Mycielski construction iteratively builds triangle-free graphs with successively higher chromatic numbers starting from the cycle C_5 (which has \chi = 3), demonstrating that \chi(G) can be arbitrarily large for triangle-free G on sufficiently many vertices; for instance, the Grötzsch graph obtained after one iteration has \chi = 4. This shows that no constant upper bound exists independent of graph parameters, contrasting with bipartite triangle-free graphs where \chi = 2.

Advanced Topics

Ramsey Theory Connections

Ramsey theory provides deep insights into the structural properties of triangle-free graphs, particularly through the off-diagonal Ramsey numbers R(3,k). The number R(3,k) is defined as the smallest integer n such that every triangle-free graph on n vertices contains an independent set of size k. Equivalently, it represents the threshold beyond which it is impossible to have a graph on n vertices that avoids both triangles and independent sets of size k. This connection highlights how Ramsey theory enforces the existence of large independent sets in sufficiently large triangle-free graphs, linking extremal graph theory with unavoidable structures.^[35] The asymptotic growth of R(3,k) is \Theta\left( \frac{k^2}{\log k} \right), establishing tight bounds on the scale at which triangle-free graphs must develop large independent sets. The upper bound R(3,k) = O\left( \frac{k^2}{\log k} \right) was proved by Ajtai, Komlós, and Szemerédi using probabilistic methods to show that random graphs with appropriate edge densities force either a triangle or a large independent set. This was asymptotically matched by Kim's lower bound construction, which demonstrates the existence of triangle-free graphs on \Omega\left( \frac{k^2}{\log k} \right) vertices with independence number less than k, achieved via a semi-random greedy algorithm that builds dense triangle-free graphs while controlling independent set sizes. These matching bounds confirm the precise order of magnitude for R(3,k).^[36] The Ramsey number R(3,k) directly implies fundamental guarantees on independent sets in triangle-free graphs, as any such graph on n vertices with n \geq R(3,k) must have an independent set of size at least k. Inverting this, for a triangle-free graph on n vertices, the independence number is at least on the order of \sqrt{n \log n}, derived from the asymptotic bounds on R(3,k). This result is pivotal in applications requiring the detection or construction of large independent sets without triangles, such as in coding theory and network design, where avoiding cliques ensures robustness while maximizing non-adjacent vertex collections.^[35]

Spectral Properties

The spectrum of the adjacency matrix A of a triangle-free graph G on n vertices with m edges provides key insights into its structural properties, particularly through bounds on the eigenvalues \lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n, where \lambda_1 is the spectral radius \rho(G). A fundamental lower bound holds for any graph: \rho(G) \geq \sqrt{2m/n}, derived from the Frobenius norm \|A\|_F^2 = \sum \lambda_i^2 = 2m and the inequality \rho(G) = \|A\|_2 \geq \|A\|_F / \sqrt{n}. For triangle-free graphs specifically, the spectrum lacks certain positive eigenvalue configurations that would indicate the presence of triangles, as triangles contribute to higher-order walk counts reflected in the powers of A; however, no simple eigenvalue threshold fully characterizes triangle-freeness without additional structure.^[37] In the subclass of strongly regular graphs, parameterized by (n, k, \lambda, \mu), the condition \lambda = 0 ensures the graph is triangle-free, since \lambda counts common neighbors of adjacent vertices. The eigenvalues are then k (with multiplicity 1) and the roots \theta, \tau = \frac{-\mu \pm \sqrt{\mu^2 + 4(k - \mu)}}{2} of the associated quadratic, with \tau < 0 < \theta. The Hoffman ratio bound yields the independence number \alpha(G) \leq n \frac{ -\tau }{ k - \tau }, providing tight structural constraints for such graphs; for example, this bound gives \alpha(G) \leq n/2 for the complete bipartite case, which is tight.^[38] A cornerstone of spectral extremal graph theory for triangle-free graphs is Nosal's theorem, which states that \rho(G) \leq \sqrt{m}, with equality if and only if G is the complete bipartite graph K_{\lfloor n/2 \rfloor, \lceil n/2 \rceil}. This refines Mantel's theorem spectrally, as the maximum m = \lfloor n^2/4 \rfloor implies \rho(G) \leq n/2. The result, originally from Nosal's 1970 thesis, has been reproved and extended using eigenvector techniques and has implications for non-bipartite cases, where stricter bounds like \rho(G) \leq \sqrt{m-1} hold.^[39]^[40] Post-2010 developments have linked spectral properties of triangle-free graphs to inequalities governing subgraph densities, notably through connections to Sidorenko's conjecture on minimum homomorphism counts for bipartite patterns. In particular, a reverse Sidorenko inequality establishes that for any triangle-free d-regular graph G and weighted graph H (allowing loops), the homomorphism density satisfies \mathbb{E}[w(H)^G] \leq (\mathbb{E}[w(K_{1,1})^G])^e(H), where equality holds for bipartite H; this provides upper bounds on densities in triangle-free hosts, contrasting the original conjecture's lower bounds in quasirandom graphs and advancing understanding of extremal densities via spectral gap analysis.^[41] Recent spectral bounds, such as \lambda_1 + \lambda_n \leq (3 - 2\sqrt{2})n \approx 0.1716n for any triangle-free G, further refine these connections by constraining eigenvalue spreads that influence density fluctuations.^[37]

References

[1]
Triangle-Free Graph -- from Wolfram MathWorld
A triangle-free graph is a graph containing no graph cycles of length three. A simple graph is triangle-free iff Tr(A^3)=0, where A is the adjacency matrix of ...
[2]
[PDF] Extremal graph theory
Extremal graph theory's basic statement is Mantel's theorem, which states that a graph with no triangles on n vertices has at most n²/4 edges.
[3]
Full article: A Simple Construction to Prove Mycielski's Theorem
Theorem 1. For any natural number k, there exists a k-chromatic triangle-free graph. Proof. For k = 1, the graph K 1 has the required property.
[4]
Mycielski Graph -- from Wolfram MathWorld
A Mycielski graph M_k of order k is a triangle-free graph with chromatic number k having the smallest possible number of vertices.Missing: high | Show results with:high
[5]
Grötzsch Graph -- from Wolfram MathWorld
The Grötzsch graph is smallest triangle-free graph with chromatic number four. It is identical to the Mycielski graph of order four, and is implemented as ...
[6]
https://www.its.caltech.edu/~dconlon/EGT1.pdf
[7]
Mantel's Theorem Explained: Proof, Examples & Uses - Vedantu
Rating 4.2 (373,000) A triangle-free graph is the central condition of the theorem. Mantel's Theorem explores the limit of how 'dense' a graph can become before this condition is ...
[8]
Cycle-maximal triangle-free graphs - ScienceDirect.com
The girth of a graph is the size of the smallest cycle, by convention ∞ if there are no cycles. Triangle-free is equivalent to having girth at least 4. A ...
[9]
Triangle-free graphs and forbidden subgraphs - ScienceDirect.com
The relation of chromatic aspects and the existence of certain induced subgraphs of a triangle-free graph will be investigated.
[10]
Existence of triangle-free graphs for regular graphs of degree at ...
Dec 10, 2010 · The union of d of these perfect matchings is a d-regular bipartite graph (and hence triangle-free). It is obviously not true if the number of ...Determine or estimate the number of maximal triangle-free graphs ...Relationship between triangle free graphs and their minimum degreeMore results from mathoverflow.net
[11]
Testing Triangle-Freeness in General Graphs
In this paper we consider the problem of testing whether a graph is triangle-free and, more generally, whether it is H-free, for a fixed subgraph H. The ...
[12]
Bipartite Graph -- from Wolfram MathWorld
A bipartite graph, also called a bigraph, is a set of graph vertices decomposed into two disjoint sets such that no two graph vertices within the same set ...
[13]
[PDF] Characterization of Bipartite Graphs - Gustavus Adolphus College
Oct 15, 2012 · Suppose G is a nontrivial, connected, bipartite graph containing an odd cycle ... If a nontrivial, connected graph G contains no odd cycles, then ...
[14]
[PDF] Math 778S Spectral Graph Theory Handout #2
Theorem 1 (König 1936) A graph is bipartite if and only if it has no odd cycle. Proof: It is sufficient to prove this for any connected graph. Necessity: Let G ...
[15]
[PDF] Chapter 4. Extremal Problems
Apr 30, 2022 · A complete k-partite graph Kn1,n2,...,nk with n = n1 + n2 + ··· + nk and |ni − nj| ≤ 1 is called a Turan graph, denoted Tn,k. Note. Of course, ...
[16]
Petersen Graph -- from Wolfram MathWorld
The Petersen graph is the cubic graph on 10 vertices and 15 edges which is the unique (3,5)-cage graph (Harary 1994, p. 175), as well as the unique (3 ...
[17]
Clebsch Graph -- from Wolfram MathWorld
A strongly regular quintic graph on 16 vertices and 40 edges with parameters (nu,k,lambda,mu)=(16,5,0,2) . In fact, it is the unique strongly regular graph ...
[18]
[PDF] Forbidding a Subgraph - Yufei Zhao
This question was answered in the early 1900's by Willem Mantel, whose theorem is considered the starting point of extremal graph theory. Let us partition the 𝑛 ...<|control11|><|separator|>
[19]
[PDF] Guessing Numbers and Extremal Graph Theory
Sep 9, 2020 · This type of question was introduced by Mantel [12] in 1907, for avoiding triangles, in a series of mathematical exercises published by the ...
[20]
https://doi.org/10.1007/s00493-013-2863-8
[21]
[PDF] 1 Triangle Counting and Matrix Multiplication
For example, choosing the adjacency matrix representation instead of, say, the adjacency list representation, allowed us to get a faster algorithm. 3. If ...
[22]
[PDF] Subcubic Equivalences Between Path, Matrix, and Triangle ...
Boolean matrix multiplication (BMM). • Detecting if a graph has a triangle. • Listing up to n2.99 triangles in a graph. • Verifying the ...
[23]
[PDF] An Improved Combinatorial Algorithm for Boolean Matrix Multiplication
Feb 26, 2017 · Abstract. We present a new combinatorial algorithm for triangle finding and Boolean matrix multiplication that runs in. ˆO(n3/ log4 n) time, ...
[24]
Finding a Minimum Circuit in a Graph | SIAM Journal on Computing
Finding minimum circuits in graphs and digraphs is discussed. An almost minimum circuit is a circuit which may have only one edge more than the minimum.
[25]
[PDF] Fast Counting of Triangles in Large Real Networks: Algorithms and ...
local triangle counting, they are more efficient. Two straightforward listing methods are the Node Iterator and the Edge Iterator algorithms. The Node Itera-.
[26]
Quantum Algorithms for the Triangle Problem - SIAM.org
We present two new quantum algorithms that either find a triangle (a copy of K 3 ) in an undirected graph G on n nodes, or reject if G is triangle free.
[27]
[PDF] Matching Triangles and Basing Hardness on an Extremely Popular ...
The vast majority of these lower bounds are based on one of three famous hypotheses: the 3-SUM conjecture, the APSP conjecture, and the Strong Exponential Time ...
[28]
[PDF] Popular conjectures imply strong lower bounds for dynamic problems
Notice that if ω = 2, then the best algorithm for triangle detection in m-edge graphs would run in O(m. 4/3) time which is still far from linear. One of the ...
[29]
Matching Triangles and Basing Hardness on an Extremely Popular ...
The vast majority of these lower bounds are based on one of three famous hypotheses: the 3-SUM conjecture, the all pairs shortest paths (APSP) conjecture, and ...
[30]
[PDF] The complexity of counting graph homomorphisms
The resulting graph describes the #P-hard problem of counting independent sets in graphs. ... a triangle, contradicting the fact that H satisfies Property 1.
[31]
[PDF] Counting Polygon Triangulations is Hard - DROPS
In 1979, Leslie Valiant published his proof that it is #P-complete to compute the permanent of a 0-1 matrix, or equivalently to count the perfect matchings ...
[32]
[PDF] ISOMORPH-FREE EXHAUSTIVE GENERATION Brendan D. McKay
Our example will be the generation of triangle-free graphs (TFGs) starting with a single vertex and repeatedly adding vertices. To keep the general description ...
[33]
[PDF] Chapter 6 - Graph Enumeration
all triangle-free graphs are bipartite. Let Bn be the number of bipartite graphs. Theorem 102 Almost all triangle-free graphs are bipartite. More precisely ...
[34]
[PDF] Independence Numbers of Triangle-free graphs (remark) Noga Alon
Theorem 2 (Ajtai, Komlós, Szemerédi) Let G = (V,E) be a triangle-free graph on n vertices with average degree d ≥ 1. Then, the independence number of G is ...<|control11|><|separator|>
[35]
A note on the independence number of triangle-free graphs
Let G be a triangle-free graph on n points with average degree d. Let α be the independence number of G. In this note we give a simple proof that α ⩾ n.
[36]
[PDF] NUMBERS IN RAMSEY THEORY - RL Graham - UCSD Math
Asymptotic bounds on classical problems. In this section we will review a few basic bounds on the numbers r(k, l) and then outline some very recent ...<|control11|><|separator|>
[37]
A note on Ramsey numbers - ScienceDirect.com
Upper bounds are found for the Ramsey function. We prove R(3, x) < cx 2 ln x and, for each k ⩾ 3, R(k, x) < c k x k − 1 ( ln x) k − 2 asymptotically in x.
[38]
Note on the sum of the smallest and largest eigenvalues of a triangle ...
May 18, 2022 · Note on the sum of the smallest and largest eigenvalues of a triangle-free graph. Let G be a triangle-free graph on n vertices with adjacency ...Missing: spectrum | Show results with:spectrum
[39]
[PDF] Spectra of graphs - CWI
The largest eigenvalue of a graph is also known as its spectral radius or index. ... Seidel & Shult [93] characterizing graphs with smallest eigenvalue not less.
[40]
[PDF] More on Nosal's spectral theorem: Books and 4-cycles
Aug 19, 2024 · Nosal's theorem states that if a graph is triangle-free, its spectral radius satisfies λ(G) ≤ √ m. An m-edge graph G is Nosal if λ(G) > √ m.
[41]
[2104.12171] On a theorem of Nosal - arXiv
Apr 25, 2021 · In 1970 Nosal proved that if \lambda_{1}^{2}>m, then G contains a triangle. In this paper we show that the same premise implies that bk\left( G\ ...
[42]
[1809.09462] A reverse Sidorenko inequality - arXiv
Sep 25, 2018 · Title:A reverse Sidorenko inequality ... for every d-regular triangle-free G. The triangle-free hypothesis on G is best possible. More generally, ...