В процессе решения задач возникло пару вопросов.
1) Как я понял, компонента рёберной двусвязности — это связный граф, в котором любые две вершины лежат на рёберно простом цикле. Мне кажется, что отсутствие мостов — это признак рёберной двусвязности графа, но доказать или опровергнуть это я не могу.
2) Пусть есть 3 произвольные вершины A, B, C (Некоторые буквы могут обозначать одну и ту же вершину). Правда ли что в компоненте рёберной двусвязности всегда существуют не пересекающиеся по рёбрам пути AB и AC?
3) Компонента вершинной двусвязности — это связный граф, в котором любые два ребра лежат на вершинно простом цикле. Является ли истиной, что отсутствие мостов и точек сочленения — это признак вершинной двусвязности графа? Если да, то почему?
Всё что я нашёл по этой теме — тык, тык
UPD. Доказательство первого факта оказалось простым, но почему-то догадался не сразу. В ссылке выше есть доказательство транзитивности двусвязности двух вершин (вершины называются двусвязными, если есть хотя-бы два, не пересекающихся по рёбрам, пути, соединяющие эти вершины). Так как для любых двух, соединённых ребром, вершин верно, что они двусвязны (так как нет мостов), то по свойству транзитивности это верно для любых пар вершин.
UPD2. Третий факт можно доказать аналогично первому, но только с тем отличием, что два смежных ребра всегда лежат на вершинно простом цикле, если отсутствуют мосты и точки сочленения.
Доказательство и пояснение второго факта в комментариях.
Надеюсь, кому-нибудь это будет полезно.
