Відношення вершинної двозв’язності

Зауважимо, що й є два різних двусвязных ребра, всі вони лежать на деякому вершинно простому циклі.

Рефлексивність:У даному випадку маємо 2 порожні шляхи, які, очевидно, не перетинаються.

Симетричність:Випливає із симетричності визначення.

Нехай маємо ребра: [math]ef[/math] вершинно двозв'язно з [math]cd[/math], [math]cd[/math] вершинно двозв'язно з [math]ab[/math], при цьому всі вони різні. Ребра [math]ef[/math] та [math]cd[/math] лежать на вершинно простому циклі [math]C[/math]. Будемо вважати, що існують шляхи, що не перетинаються [math]P : a \leadsto c[/math] , [math]Q : b \leadsto d[/math] (ситуація, коли вони йдуть навпаки, розбирається аналогічно). Нехай [math]x[/math] — перша вершина на [math]P[/math] , що також лежать на [math]C[/math] , [math]y[/math] — перша вершина на [math]Q [/ Math] , що лежить на [ Math] C [/ Math] . Зробивши шляхи від [math]a[/math] до [math]x[/math] і від [math]b[/math] до [math]y[/math] , далі підемо по циклу [math]C[/ math] у потрібні (різні) сторони, щоб досягти [math]e[/math] і [math]f[/math]. Тобто [math]ef[/math] вершинно двозв'язно з [math]ab[/math].

Зауваження.Розглянемо таке визначення: вершини [math]u[/math] і [math]v[/math] називаються вершинно двозв'язковими, якщо між ними існують 2 шляхи, що не перетинаються по вершинах, за винятком кінців. Це визначення неспроможна претендувати на коректність, оскільки у разі ставлення вершинної двусвязности перестане бути транзитивним.

---