Добрый день.
Возникли затруднения с, казалось бы, простым вопросом: какое минимальное значение числа независимости может иметь двудольный граф на n вершинах (при n >= 10)?
Я рассуждал так, что если у нас граф двудольный, то в худшем случае у нас оба подмножества вершин равны n/2, следовательно и минимальное значение числа независимости будет n/2. И картинка для моих рассуждений:
