Верхняя оценка количества рёбер в графе, дополнение $k$-ой степени которого связно

Назовем граф $k$-широким, если для любого разбиения его вершин на два множества, в них найдутся вершины на растоянии не менее $k$ (то есть, дополнение $k$ степени этого графа связно). Назовем граф $k$-моношироким, если для любого разбиения его вершин на два множества, в них найдутся вершины на растоянии $k$.
В работе доказано, что в дополнении $3$-широкого графа на $n$ вершинах не менее чем $3n-7$ ребер, а в дополнении $3$-моноширокого графа на $n$ вершинах не менее чем $3n-8$ ребер. Приводятся бесконечные серии примеров, подтверждающих точность оценок.
Также доказана асимптотически точная оценка для случая $k\ge4$: в дополнении $k$-широкого графа не менее чем $(n-2k)(2k-4[\log_2k]-1)$ рёбер. Библ. – 6 назв.