Сколько вершин графа надо покрасить?!

[TelmanStud]

Доброго времени суток.
Помогите пожалуйста с задачей.
Количество вершин связного графа равно $N$. Известно, что каждая вершина имеет степень $n$. Вершинная связность равна $m$.
1) Сколько вершин минимум можно закрасить (в зависимости от вида графа), чтобы каждая вершина была смежна хотя бы с одним закрашенным?
2) При каком минимальном количестве закрашенных вершин, независимо от вида графа каждая вершина будет смежна хотя бы с одним закрашенным?

При $m=1$ ответ на первый вопрос кажется выходит $\frac{N}{n-1}$.
Однако при $m\ne 1$ не могу ничего сообразить.
Автор задачи я, поэтому не уверен в достаточности исходных данных.

[Pphantom]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:

- все-таки какие-нибудь собственные содержательные попытки решения задачи надо предложить.

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Pphantom]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»