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)
Wikimedia FoundationIn Group: Ramsey Theory and Extremal Combinatorics, Lead or opening section
It is one of the central results of extremal graph theory, an area studying the largest or smallest graphs with given properties
- In Branch: Graph Theory, Lead sentence
View the Source 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.