Ответы и пояснения

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

Следствие. Связный граф не имеет точек сочленения тогда и только тогда, когда он является 2-связным.

2. Если в связном графе без петель через любые две вершины проходит элементарный цикл, то после удаления одной вершины (вместе со всеми инцидентными ей ребрами) между любой парой оставшихся вершин всегда будет существовать элементарная цепь. Поэтому граф не может иметь точек сочленения. Обратно, если граф не имеет точек сочленения, то он является 2-связным. Поэтому любые две его вершины А и В соединяются двумя простыми путями, не имеющими общих промежуточных вершин. Объединение этих путей образует простой цикл, проходящий через А и В.

Рис. 36.

3. Ясно, что если через любые два ребра связного графа без петель проходит элементарный цикл, то граф является 2-связным и не имеет точек сочленения. Обратно, пусть связный граф без петель не имеет точек сочленения. Докажем, что через любые два его ребра а и b проходит элементарный цикл. Доказательство проведем для наиболее сложного случая, когда ребра а и b не являются смежными. Обозначим через А] и А2 граничные вершины ребра я, а через Вi и В₂ — граничные вершины _ ребра Ъ (см. рис. 36).

Граф является связным, поэтому между вершинами А] и В/ существует простая цепь (Li). Тогда и между вершинами А₂ и В₂ существует простая цепь (a, L/, Ь). Но так как граф не имеет точек сочленения, то он является 2- связным и между, вершинами В₂ и А₂ должна существовать еще одна простая цепь (L₂), не имеющая с цепью (a, L/, Ь) общих промежуточных вершин; Следовательно, через ребра а и b проходит простой цикл, являющийся объединением цепей (Li) и (a, L_:. b).

Рис. 37.

4. Пусть множество вершин связного графа G разбито на два не пустых подмножества W_t и W₂ (см. рис. 37), и пусть (L)=a_l, a₂,…, a_n- замкнутый маршрут, который начинается и кончается в вершине А, принадлежащей одному из подмножеств Wi или W? (например — W/).

Начиная движение из вершины А по маршруту (L) и возвращаясь в эту вершину, мы перейдем из множества W_t во множество W₂ столько же раз, сколько перейдем из W₂ в IV/. Поэтому общее количество ребер,' разделяющих множества W/ и W₂ и принадлежащих маршруту (L), является четным.

• 5. Пусть ребро е является перешейком связного графа G. Обозначим через W/ и W₂ множества вершин графа G, которые разделяются ребром е, и пусть Ае W_t, Be W₂. Докажем, что каждая цепь, соединяющая А и В, проходит через е. Действительно, если бы в графе G существовала цепь, не проходящая через е, то после удаления ребра е вершины А и В остались бы связными. Мы получили противоречие с тем, что ребро е является перешейком и разделяет Wi и Щ ? Обратно, если в связном графе G существует такая пара вершин А и В, что любая соединяющая их цепь проходит через ребро е, то после удаления этого ребра между вершинами А и В не будет существовать цепи (т.е. получится несвязный граф). Следовательно, е — перешеек.
• 6. Пусть в связном графе G ребро е является перешейком. Обозначим через А и В граничные вершины ребра е. Если бы ребро е содержалось в некотором цикле, тогда вершины А и В остались связными после удаления ребра е. Это противоречит определению перешейка. Обратно, пусть в связном графе G ребро е не принадлежит ни какому циклу. Тогда граничные вершины А и В ребра е соединены единственной цепью (ребром е), и после удаления ребра е граф G перестанет быть связным. Следовательно, е — перешеек.
• 7. Если граф является^{-связным,} то любая пара его вершин А и В соединяется по меньшей мере к цепями, не имеющими общих ребер. Поэтому для нарушения связности между А и В потребуется удалить не менее к ребер (по одному на каждой цепи, соединяющей А и В). Следовательно, разделяющие множества этого графа содержат не менее к элементов.
• 8. Удалим произвольное ребро исходного графа.

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

9. Полный граф с п вершинами является (и — /)-связным, и разделяющее множество (частным случаем которого является простой разрез) должно содержать не менее п — 1 ребра. Очевидно, что если удалить все ребра, инцидентные некоторой вершине полного графа, то получим простой разрез, содержащий п -1 ребро.