【摘要】 Ramsey定理指出:对于任何一个正整数k,存在一个最小的正整数r(k,k),使得对任意一个至少有r(k,k)个顶点的图G,它或者有k个顶点的完全子图Kk,或者有k个顶点是独立集.由此定理易得:设G是顶点数n>r(k,k)的简单图,其边数e>0,且G的所有k阶导出子图的边数相等,那么G是完全图.并给出上述结论的推广:设G是n(n≥4)阶简单图,其边数e>0,对某个给定的自然数k(2≤k≤n-2),若G的所有k阶导出子图的边数相等,则G是完全图.更多还原

【Abstract】 Ramsey showed that, given any positive integer k, there exists a smallest integer r(k,k) such that every graph on r(k,k) vertices contains either a complete subgraph Kk, or an independent set of k vertices. This theorem implies immediately that, if G is a simple graph on n(≥r(k,k)) vertices, the edgenumber>0, and every induced subgraph with k vertices of G has the same edgenumber, then G is a complete graph.A refinement of the above result is obtained, and it is proved that, if G is a simple graph on n(≥4) vertices, the edgenumber e>0, and for given positive integer k(2≤k≤n-2), every induced subgraph with k vertices of G has the same edgenumber, then G is a complete graph.更多还原