Задача на графы

[prrrr]

Здравствуйте! Вроде понимаю, как решить, но строгое доказательство не получается. Подскажите пожалуйста, что я упускаю?

Задача:
В графе на $20$ вершинах при удалении любых двух ребер образуется не более двух компонент связности. Какое наименьшее количество ребер может быть в таком графе?

Мое решение:
Чтобы убрать два ребра и получить не более двух компонент связности, изначальный граф должен быть связным, иначе в нем уже присутсвовало бы больше одной компненты связности (не менее двух). Связный граф с минимальным количеством ребер, который при удалении двух ребе образует не более двух компонент связности имеет конфигурацию замкнутого контура по всем $20$ вершинам и минимальное количество ребер в таком графе равно $20$.
Мы получили минимально возможное количество ребер равное $20$. Рассмотрим возможно ли получить подобный граф с меньшим количесвтом ребер, удовлетворяющий условию задачи.

Минимально возможно построить связный граф (в несвязном графе уже присутствуют не менее двух компонент связности, до удаления ребер) с $20$ вершинами и $19$ ребрами. В этом графе будет $2$ вершины степени $1$ и $18$ вершин степени $2$.

Рассмотрим, будет ли возможность получить не более двух компонент связности, удалив из данного графа $2$ ребра? После удаления двух ребер, общее количество ребер становится равно $17$, но вершин по прежднему $20$. Это значит, что в графе не более $18$ вершин степени $2$ и $2$х верхин степени $0$, т.е. не менее $3$х компонент связности, что противоречит условию.

Следовательно $20$ - минимальное возможное количество ребер в графе, удовлетворяющем условию задачи.

[Sender]

prrrr в сообщении #1519027 писал(а):

Минимально возможно построить связный граф (в несвязном графе уже присутствуют не менее двух компонент связности, до удаления ребер) с $20$ вершинами и $19$ ребрами.

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

prrrr в сообщении #1519027 писал(а):

В этом графе будет $2$ вершины степени $1$ и $18$ вершин степени $2$.

А вот это, вообще говоря, неверно.

[mihaild]

prrrr в сообщении #1519027 писал(а):

изначальный граф должен быть связным, иначе в нем уже присутсвовало бы больше одной компненты связности

А почему это противоречит условию? Может граф несвязный, но после удаления двух любых рёбер число компонент связности не увеличивается? Например два полных графа на 10 вершинах каждый.

[prrrr]

Sender в сообщении #1519044 писал(а):

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

Да, конечно это деревья.

Sender в сообщении #1519044 писал(а):

А вот это, вообще говоря, неверно.

Я получается взял частный случай дерева, когда все вершины выстроеныв одну линию.

-- 18.05.2021, 15:00 --

mihaild в сообщении #1519046 писал(а):

А почему это противоречит условию? Может граф несвязный, но после удаления двух любых рёбер число компонент связности не увеличивается? Например два полных графа на 10 вершинах каждый.

Точно, я уже потом об этом подумал. Но тут получается, что:
- в задаче указано требование о минимальном количестве ребер в графе, поэтому полный граф мы взять не можем, только два графа в виде замкнутых контуров на 10 вершинах с 10 ребрами каждый;
- в этом случае нельзя удалить два любых ребра, т.к. если ребра принадлежат к одному графу, то при удалении двух ребер он разделяется минимум на два графа и общее число компонент связности становится равным трем.

-- 18.05.2021, 15:14 --

Доработал решение получается так:
Рассмотрим возможные варианты построения графа, удовлетворяющие условию задачи:

1). Связный граф. Связный граф с минимальным количеством ребер, который при удалении двух ребер образует не более двух компонент связности имеет конфигурацию замкнутого контура по всем 20 вершинам и минимальное количество ребер в таком графе равно 20. Меньшее количество ребер невозможно, т.к. в этом случае число компонент связности, при удалении двух ребер становится равным не менее чем трем. Например, связный граф на 20 вершинах с 19 ребрами - это дерево. При удалении двух ребер в данном дереве получается не менее трех компонент связности.

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

Следовательно единственный граф, который удовлетворяет условию задачи по минимальному количеству ребер и образованию после удаления двух ребер не более двух компонент связности - это граф в виде замкнутого контура с 20 ребрами.

[Sender]

prrrr в сообщении #1519085 писал(а):

в задаче указано требование о минимальном количестве ребер в графе, поэтому полный граф мы взять не можем, только два графа в виде замкнутых контуров на 10 вершинах с 10 ребрами каждый;

Вообще говоря, необязательно брать полные графы, в качестве компонент подошли бы, скажем, и 3-рёберно связные графы. Одна из них вообще может состоять из одной-единственной вершины.

[Евгений Машеров]

(Оффтоп)

prrrr в сообщении #1519027 писал(а):

который при удалении двух ребе

Духовных лиц обижают!