Я не верю, что на этот вопрос есть простой ответ (как это часто бывает с проблемами с Рэмси), но вот подход, чтобы вы начали (я предполагаю, что это домашняя работа, и поэтому я не будупопробуйте все до конца).
Предположим, что граф связан (без этого предположения проблема только усложняется).Пусть 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) ребер).