具有n个顶点和m个边的图的最小团数（即最大团大小）是什么？我想用图兰定理，但这只告诉我们，给定团数，边数的上界。我已经被困在这里好几天了，需要帮助。
最佳答案
我不相信这个问题有一个简单的答案（拉姆齐式的问题经常是这样的），但这里有一个方法让你开始（我假设这是家庭作业，所以我不会试图一路解决）。
假设图是连通的（没有这个假设，问题只会变得更困难）。让k成为可能的最小集团数。极端情况是：
如果n = m-1（等价地，图形是树），则k=2。
如果m = (n choose 2)（等价地，图形是完整的），则k=n。
由此可以合理推断，当m相对于n增加时，k也应该增加继续这个想法，看看它会把你带到哪里。
我计算出了小的n,m的数字，结果不在OEIS中，尽管我可能犯了一个计算错误（如果你找到了，请告诉我）以下是数字：
n\m | 0 1 2 3 4 5 6 7 8 9 10
---------------------------
1 | 1 - - - - - - - - - -
2 | - 2 - - - - - - - - -
3 | - - 2 3 - - - - - - -
4 | - - - 2 2 3 4 - - - -
5 | - - - - 2 2 2 3 3 4 5
6 | - - - - - 2 2 2 2 2 3
同样，我假设连接（至少
n-1边）并且没有循环（最多(n choose 2)边）。