Grafové operace
Úloha číslo: 3815
Nechť \(k_v(G)\) značí vrcholovou a \(k_e(G)\) hranovou souvislost grafu \(G\).
Varianta
Dokažte, že pro graf \(G\) a hranu \(e \in E(G)\) platí \(k_e(G) - 1 \leq k_e(G - e) \leq k_e(G)\).
Varianta
Dokažte, že pro graf \(G\) a vrchol \(v \in V(G)\) platí \(k_v(G) - 1 \leq k_v(G - v) \).
Varianta
Sestavte graf \(G\), pro nějž platí: \(k_v(G - v) \not\leq k_v(G) \).
Varianta
Dokažte, že smazání hrany nesníží vrcholovou souvislost grafu o více než 1.
Jinými slovy, že \(k_v(G/e) \ge k_v(G)-1\).
Varianta
Dokažte, že kontrakce hrany nesníží vrcholovou souvislost grafu o více než o 1.
Jinými slovy, že \(k_v(G/e) \ge k_v(G)-1\).