Láttunk példákat összefüggő és nem összefüggő gráfokra. Míg a “nem összefüggő” eléggé zsákutca, sokat lehet mondani arról, hogy “mennyire összefüggő” egy összefüggő gráf.A legegyszerűbb megközelítés az, hogy megnézzük, mennyire nehéz egy gráfot szétkapcsolni csúcsok vagy élek eltávolításával. Feltételezzük, hogy minden gráf egyszerű.
Ha egy gráfot egyetlen csúcs, úgynevezett vágási pont eltávolításával szét lehet választani, akkor azt mondjuk, hogy a gráf összefüggő1. Ha ez nem lehetséges, de a gráf szétkapcsolható két csúcs eltávolításával, akkor a gráfnak 2 összekapcsolhatósága van.
Az élekkel ugyanígy járunk el:
5.7.3. tétel $\kappa(G)\le\lambda(G)$.
A 2-összeköttetésű gráfok különösen fontosak, és a következő egyszerű tétel hasznos.
A 2-összekapcsolt gráfoknak vannak más szép jellemzései is.
A következő következmény a tétel egyszerű újrafogalmazása.
A tételnek ez a változata egy általánosítást javasol:
Először bizonyítsuk Menger eredeti, “lokális” változatát.
5.7.9. tétel Ha $v$ és $w$ a $G$ nem szomszédos csúcsai, akkor $\kappa_G(v,w)=p_G(v,w)$.
$$\bullet\quad\bullet\quad\bullet\quad\bullet$$
Röviden visszatérünk a 2-összekapcsolhatósághoz.A következő tételt néha arra használhatjuk, hogy egy indukciós bizonyításban megadjuk az indukciós lépést.
A nem összefüggő gráf összefüggő összetevőkből áll. Az erre emlékeztető tételben azt látjuk, hogy a nem2összekapcsolt összefüggő gráfok 2összekapcsolt részgráfokból és hidakból épülnek fel.
5.7.11. definíció Egy $G$ gráfban a blokk olyan maximálisan indukált részgráf, amelynek legalább két csúcsán nincs vágási pont.
A szokásos módon a maximális itt azt jelenti, hogy a $B$ indukált részgráf nem lehet nagyobb csúcsok vagy élek hozzáadásával (a kívánt tulajdonság megtartása mellett, ebben az esetben vágási pontok nélkül).A blokk vagy egy 2 összefüggő indukált részgráf, vagy egyetlen él a végpontjaival együtt. A blokkok nagyrészt e tétel miatt hasznosak:
5.7.12. tétel $G$ blokkjai felosztják az éleket.
Ha $G$-nek egyetlen blokkja van, akkor vagy $K_2$ vagy 2-összeköttetésű, és minden 2-összeköttetésű gráfnak egyetlen blokkja van.
5.7.13. tétel Ha $G$ összefüggő, de nem2-összekapcsolt, akkor minden olyan csúcs, amely két blokkban van,$G$ metszéspontja.
GYakorlatok 5.7
Feladat 5.7.1Tegyük fel, hogy egy $n\ge 2$ csúcsú $G$ egyszerű gráfnak legalább $\ds {(n-1)(n-2)\over2}+1$ éle van. Bizonyítsuk be, hogy $G$ összefüggő.
Ex 5.7.3Tételezzük fel, hogy $G$ egyszerű, és $d_1\le d_2\le\cdots\le d_n$, és $k\le n-d_n-1$ esetén $d_k\ge k$. Mutassuk meg, hogy$G$ összefüggő.
Ex 5.7.4 Emlékezzünk, hogy egy gráf $k$-szabályos, ha minden csúcsa $k$ fokú. Mi az a legkisebb egész szám $k$, amelynél ez igaz:
Ha $G$ egyszerű, $n$ csúcsa van, $m\ge k$, és $G$ $m$-reguláris, akkor $G$ összefüggő.
(Természetesen $k$ függ $n$-től).)
Ex 5.7.6Keresünk egy egyszerű gráfot, amelynek$\kappa(G)
Megjegyezzük, hogy egy vágási pont legalább két blokkban van, így a blokk-vágási pont gráf minden függő csúcsa blokk. Ezeket a blokkokat végblokkoknak nevezzük.
Példa 5.7.10Rajzoljuk meg az alábbi gráf blokk-vágópont gráfját.