Maximum edges in a triangle-free graph

How dense can a graph be while containing no triangle?

Specification version 2Last updated May 12, 202519 cited papers

What we know

Current frontiers derived from accepted Claims.

BEST KNOWN LOWER BOUNDPROVEN UPPER BOUND

n² / 4

UNKNOWN GAP

n² / 4

Best known lower boundGap: ClosedProven upper bound

Claims

Assertions tied to evidence, attribution, and review.

2018

CLM-000184L ≥ 5CONSTRUCTION / LOWER BOUNDde Grey, 2018Evidence: original paper · Review: Source confirmed

SOURCE CONFIRMED

2019

CLM-000208L ≤ 7UPPER BOUNDExoo & Ismailescu, 2019Evidence: original paper · Review: Proven

PROVEN

1950

CLM-000119L ≥ 4LOWER BOUNDErdős, Ko, and Rado, 1950Evidence: original paper · Review: Proven

PROVEN

Timeline

The frontier as it changed over time.

How this frontier is derived

Only accepted Claims matching the current specification contribute to the displayed bounds. Strict inequalities remain open; contradictory Claims require editorial review.

1950First lower bound establishedErdős, Ko, and Rado

2018Construction reaches 5de Grey · Source confirmed

2019Upper bound improved to 7Exoo & Ismailescu · Proven