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

Question

На самом деле это не сильно связано с анализом алгоритма, но, поскольку я не смог получить значительный результат от Google, я хотел бы получить некоторое мнение.

Итак, определение двунаправленного неориентированного графа - это связный граф, который не разбивается на несвязные части путем удаления какой-либо одной вершины (из Википедии).Но у меня есть вершина, в которой удаление любого ребра из него нарушает двусвязность графа.

Я пытаюсь доказать, что у такого графа может быть не более 2n-3 ребер (где n - количество вершин).

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

Или есть что-нибудь, что вы можете мне предложить прочитать?

Answer 1

Любой граф, представляющий собой кольцо с> 3 вершинами, удовлетворяет этому критерию.

Удаление любого из синих ребер ниже означает, что удаление красной вершины создает отсоединенные части графа.

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

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

График в этом формате имеет (n-2) * 2 ребра - так что 2n-4, что намного ближе к пределу, выищу.