Mantel's Theorem states that a triangle-free graph on n vertices has at most floor of n squared over four edges, a bound achieved exactly by the complete bipartite graph that splits the vertices into two halves as evenly as possible. Named for Willem Mantel, it is the earliest and simplest case of extremal graph theory's general study of how many edges a graph can have while avoiding a forbidden subgraph, later generalized by Turan's Theorem.
Facts
StatementThe maximum number of edges in a triangle-free graph on n vertices is the floor of n squared over four. 1 Classification
Statement Form Connections
Has Statement Form
In Branch
Source Turan's Theorem (Wikipedia)
Sources
1. Mantel's theorem - Wikipedia
Lead section
The special case of the theorem for triangle-free graphs is known as Mantel's theorem; it was stated in 1907 by Willem Mantel, a Dutch mathematician.
Lead section, second sentence
it was stated in 1907 by Willem Mantel, a Dutch mathematician.
View the SourceTuran's Theorem (Wikipedia)
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.