1. При каком минимальном n существует граф на n вершинах, такой

1. При каком минимальном n существует граф на n вершинах, такой, что и он сам и его дополнение связны?
2. Известно, что граф на 100 вершинах содержит клику (множество попарно соединенных вершин) на 50 вершинах и имеет 1276 ребер. Может ли граф оказаться связным?
3. В поселке 70 пенсионерок. 1 января одна из них узнала интересную новость и сообщила ее всем своим подругам-пенсионеркам. 2 января те сообщили новость всем своим подругам-пенсионеркам, и так далее. Может ли так случиться, что:
а) 1 февраля еще не все пенсионерки будут знать новость, а 1 марта уже все? б) 1 апреля еще не все пенсионерки будут знать новость, а 1 мая уже все?
4. В графе G на 13 вершинах не менее 20 различных простых циклов длины 12. Верно ли, что G связен?
5. В связном графе степени всех вершин четные. Докажите, что граф останется связным и после удаления любого из ребер.