Hranová versus vrcholová souvislost

Ukažte, že každý vrcholově dvousouvislý graf je hranově dvousouvislý.

(Hranově dvousouvislý graf je takový, že po odebrání libovolné hrany zůstane souvislý.)

Řešení
Má-li graf most a přitom to není \(K_2\), potom alespoň jeden z konců tohoto mostu sousedí s nějakým jiným vrcholem a sám tvoří artikulaci.
Varianta
Nalezněte nejmenší graf, který je hranově dvousouvislý, ale není vrcholově dvousouvislý.
Odpověď
Nejmenší takový je graf na pěti vrcholech získaný sloučením dvou trojúhelníků ve vrcholu.
Varianta
Pro libovolnou dvojici přirozených čísel \(k \geq l \geq 2\) nalezněte graf, jehož hranová souvislost je \(k\) a vrcholová souvislost je \(l\).
Řešení
Vezmeme dva úplné grafy \( K_{k + 1} \) a spojíme je přes \( l \) společných vrcholů.

Nejmenší vrcholovým řezem je \( l \) společných vrcholů.

Nejmenší hranový řez tvoří hrany incidentní s jakýmkoli vrcholem stupně \( k \).