Вершинная связность графа

[kot_matroskin]

Доброго времени суток всем. У меня возникла такая проблемка: на зачете попалась задачка
. Узнав новость, госпожа 1 сообщает ее своим знакомым дамам; та, в свою очередь, своим знакомым, и т.д. Наконец, новость становится известна всем дамам. Какое наименьшее число дам должно внезапно оне¬меть, чтобы НОВОСТЬ, сообщенная госпожой 1, никогда не стала известной
всем дамам?
Знакомые госпожи 1: 2,3,4,7
Знакомые госпожи 2: 1,3,4
Знакомые госпожи 3:1,2,6,8
Знакомые госпожи 4: 1,2,5
Знакомые госпожи 5: 4,6,7,8
Знакомые госпожи 6: 3,5,7,8
Знакомые госпожи 7: 1,5,6,8
Знакомые госпожи 8: 3,5,6,7
Насколько я понял, задача сводится к отысканию вершинной связности графа. Ее нужно решить без использования критерия. (например "методом пристального всматривания")
Собственно говоря, у меня получилось 4. Преподаватель сказал, что он сомневается, и по его мнению ответ 3. Его авторитету я доверяю больше чем в себе в таких вопросах. Но все таки, кто не прав? И какие еще методы можно использовать при решении этой задачи?

[Cash]

Ничего не рисуя и смотря только на первые 2 ваши строчки (дальше не смотрел) заметил, что если онемеют дамы 3, 4, 7 то новость дальше круга (1, 2, 3, 4, 7) никуда не пойдет.