Ответ: минимальное число рёбер равно
$$m_{\min }=\lfloor \frac{(k-1)(n-1)}{2}\rfloor +1,$$ то есть любое (связанное) неориентированное графа на $n$ вершинах с более чем $\frac{(k-1)(n-1)}{2}$ рёбрами обязательно содержит простой цикл длины как минимум $k$. Этот результат — классическая теорема Эрёша–Галлаи (Erdős–Gallai).
Краткое доказательство (со счётом «назад», классический аргумент Эрёша–Галлаи).
1) Пусть $G$ — граф на $n$ вершинах без простых циклов длины $\ge k$. Возьмём упорядочение вершин $v_1,v_2,\dots ,v_n$ так, чтобы для каждого $i$ число соседей $v_i$ среди предыдущих вершин минимально (подходит и упорядочение по концам максимального пути; в классическом доказательстве берут любую последовательность, полученную из максимального пути). Обозначим
$$b_i=|\{j<i:v_j{v}_i\in E(G)\}|.$$ Тогда число рёбер $e(G)={\sum }_{i=1}^n{b}_i$.
2) Утверждение: для каждого $i$ имеем
$$b_i\le \min \{i-1,k-1\}.$$ Действительно, очевидно $b_i\le i-1$. Если же для некоторого $i$ было бы $b_i\ge k$, то среди соседей $v_i$ среди предыдущих вершин найдутся $k$ вершин $u_1,\dots ,u_k$ в порядке их появления; тогда в графе можно построить простой цикл длины $\ge k$ (комбинируя ребро к $v_i$ и пути между соответствующими $u_j$ в уже рассмотранной части), что противоречит ограничению на длину циклов. (Этот шаг — стандартный аргумент из доказательств Эрёша–Галлаи: наличие $k$ «предыдущих» neighbours даёт цикл длины $\ge k$.)
3) Следовательно
$$e(G)=\sum _{i=1}^n{b}_i\le \sum _{i=1}^n\min \{i-1,k-1\}=\sum _{t=0}^{k-2}t+(n-(k-1))(k-1)=\frac{(k-1)(n-1)}{2}.$$
Это даёт оценку сверху для числа рёбер в графе без циклов длины $\ge k$. Поэтому при
$$e(G)>\frac{(k-1)(n-1)}{2}$$ вынужденно существует простой цикл длины хотя бы $k$. Из целочисленных соображений минимальное целое $m$, гарантирующее наличие такого цикла, равно
$$m_{\min }=\lfloor \frac{(k-1)(n-1)}{2}\rfloor +1.$$
Острота оценки. Конструкция, достигающая равенства (показывающая, что оценка в общем случае точна) строится рекурсивно: возьмём упорядочение вершин $v_1,\dots ,v_n$ и соединим каждую вершину $v_i$ с ровно $\min \{i-1,k-1\}$ предыдущими вершинами (для первых $k$ вершин это даёт клику на $k$ вершинах, затем каждая следующая вершина соединена ровно с $k-1$ предыдущими). В таком графе нет цикла длины $\ge k$, и число рёбер равно ровно $\frac{(k-1)(n-1)}{2}$ (если требуется целая величина, берётся целочисленная версия), так что порог нельзя понизить.
Связь с теоремами Турэна и дальнейшие обобщения.
- Теорема Эрёша–Галлаи прямо даёт границу по числу рёбер для наличия длинного цикла; Турánова теорема даёт экстремум числа рёбер при запрещении клики $K_r$ (другая «задача экстремума»). Оба результата относятся к классическим задачам экстремальной теории графов, но решают разные запреты (длинные циклы vs большие клики / отсутствующие подграфы).
- Обобщения и уточнения: существуют условия в терминах минимальной степени (Dirac, Ore), утверждающие более сильные достаточные условия для наличия гамильтонова цикла ($k=n$). Есть также результаты типа Пóсы, Чао–Фарбер и т.д., дающие критерии для циклов заданной длины с учётом распределения степеней (а не только общего числа рёбер). Наконец, существуют уточнения для 2-связных графов, для ориентированных графов и для вопросов «пэнцикличности» (наличие циклов всех длин от 3 до $n$).
Итого: порог по числу рёбер, гарантирующий наличие простого цикла длины хотя бы $k$, равен $\lfloor \frac{(k-1)(n-1)}{2}\rfloor +1$; это — содержимое теоремы Эрёша–Галлаи, связанное с другими фундаментальными результатами экстремальной теории графов (Турán, Dirac, Ore, Pósa и т.д.).