Упражнения. 
Геометрическая теория графов

1. Докажите, что вершина А связного графа тогда и только тогда является точкой сочленения, когда существуют две такие вершины В и С, что каждая цепь, соединяющая В и С, проходит через А.

2. Докажите, что связный граф без петель не имеет точек сочленения тогда и только тогда, когда через любые две его вершины проходит элементарный цикл.

3. Докажите, что связный граф без петель не имеет точек сочленения тогда и только тогда, когда через любые два его ребра проходит элементарный цикл.

4. Докажите, что в связном графе замкнутый маршрут (каждый цикл) имеет с произвольным разрезом четное число (возможно, равное нулю) общих ребер.

5. Докажите, что ребро е в связном графе является перешейком тогда и только тогда, когда существуют две такие вершины A w В, что каждая цепь, соединяющая Aw В, проходит через е.

6. Докажите, что ребро в связном графе является перешейком тогда и только тогда, когда оно не входит ни в один из циклов.

7. Докажите, что если граф является А:-связным, то он не может содержать разделяющего множества, состоящего менее чем из к ребер.

8. Связный граф имеет п ребер, каждое из которых является перешейком. Сколько вершин имеет граф?

9. Какое минимальное количество ребер имеет простой разрез в полном графе с п вершинами?