Math 2.0

Combinatorics Extremal combinatorics Theorem

Mantel's theorem

Builds on Complete graph

Statement

Let GG be a finite simple graph with nn vertices and no cycle of length 33. Then GG has at most ⌊n2/4⌋\lfloor n^2/4 \rfloor edges.

Remarks

The bound is sharp: the complete bipartite graph K⌊n/2⌋,⌈n/2⌉K_{\lfloor n/2 \rfloor, \lceil n/2 \rceil} has no triangle and has ⌊n2/4⌋\lfloor n^2/4 \rfloor edges. The theorem is the case r=2r = 2 of Turán's theorem.

History

Willem Mantel stated the theorem in 1907.

Reading path

To understand this page from the ground up, read these 2 pages in order. The foundations come first.

Show the path as a graph
Complete graph, example, no evidence levelComplete graphexampleMantel's theorem, statement, no evidence levelMantel's theoremstatement
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Complete graph example
  2. Mantel's theorem statement

Further reading

  1. Web https://en.wikipedia.org/wiki/Turán's_theorem, Mantel's theorem
About this page
Tag0MXEHSCYCS
URIm2://0MXEHSCYCS
Kindstatement, theorem
WritingW0 stub
MSC05C35
StatusThis copy of the site has no build data. Run m2 status 0MXEHSCYCS.
UsesComplete graph

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.