Extremal graph theory
Extremal graph theory
复制标题
DOI：
10.1201/b16132-57
复制
发表时间：
2009
影响因子：
4.7
通讯作者：
J. Pach;Pankaj K. Agarwal
中科院分区：
文献类型：
--
作者：
J. Pach;Pankaj K. Agarwal
极值图论的基本陈述是曼特尔定理，在1907年证明，它指出任何n个顶点上没有三角形的图最多包含n 2/4条边。这显然是最好的可能，因为可以将n个顶点的集合划分为大小为bn/2c和dn/2 e的两个集合，并在它们之间形成完全二分图。这个图没有三角形和bn 2/4c边。作为热身，我们将给出这个简单而基本的定理的一些不同的证明。
The basic statement of extremal graph theory is Mantel’s theorem, proved in 1907, which states that any graph on n vertices with no triangle contains at most n2/4 edges. This is clearly best possible, as one may partition the set of n vertices into two sets of size bn/2c and dn/2e and form the complete bipartite graph between them. This graph has no triangles and bn2/4c edges. As a warm-up, we will give a number of different proofs of this simple and fundamental theorem.