派系数量下界

Question

对于具有 n 个顶点和 m 个边的图，可能的最小团数（即最大团大小）是多少？我正在考虑使用图兰定理，但这只是告诉我们给定团数的边数的上限。我已经被困在这个问题上好几天了，需要一些帮助。

Answer 1

我不相信这个问题有一个简单的答案（拉姆齐式问题经常出现这种情况），但这里有一个让你开始的方法（我假设这是家庭作业，所以我不会尝试工作一切都出来了）。

假设该图是连通的（如果没有这个假设，问题只会变得更困难）。令k 为可能的最小团数。极端情况是：

• 如果n = m-1（相当于，该图是一棵树），则k=2。

• 如果m = (n select 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 select 2) 边）。