Дано: Связный граф.
Найти: Доказать, что можно удалить вершину вместе со всеми выходящими из нее ребрами так, чтобы граф остался связным.
Решение:
1. Если граф содержит одну вершину, то удаление ее оставит пустой граф, который также является связным.
2. Если граф содержит более одной вершины, то выберем любую вершину v и удалим ее вместе со всеми инцидентными ребрами.
3. Так как граф был связным до удаления вершины v, то каждая вершина, смежная с вершиной v, все еще связана с остальными вершинами графа через другие вершины.
4. После удаления вершины v граф все еще остается связным.
Ответ:
В любом связном графе можно удалить вершину вместе со всеми выходящими из нее ребрами так, чтобы он остался связным, так как удаление вершины не разъединит граф, а связность будет сохранена через другие вершины.