Olemme nähneet esimerkkejä kytkeytyneistä kuvaajista ja kuvaajista, jotka eivät ole kytkeytyneitä. Vaikka ”ei-kytkeytynyt” on aika lailla umpikuja, on paljon sanottavaa siitä, ”kuinka kytkeytynyt” kytkeytynyt graafi on.Yksinkertaisin lähestymistapa on tarkastella, kuinka vaikeaa on katkaista graafi poistamalla kärkipisteitä tai reunoja. Oletamme, että kaikki graafit ovat yksinkertaisia.
Jos graafi on mahdollista katkaista poistamalla yksittäinen huippu, jota kutsutaan leikkauspisteeksi, sanomme, että graafi on kytkeytyvä1. Jos tämä ei ole mahdollista, mutta on mahdollista irrottaa kuvaaja poistamalla kaksi kärkeä, kuvaajalla on liitettävyys 2.
Tehdään sama asia reunoille:
Teoreema 5.7.3 $\kappa(G)\le\lambda(G)$.
Graafit, jotka ovat 2-kytkentäisiä, ovat erityisen tärkeitä, ja seuraava yksinkertainen lause on hyödyllinen.
On muitakin mukavia luonnehdintoja 2-yhteydellisille graafeille.
Seuraava korollari on helppo uudelleenmuotoilu tästä lauseesta.
Tämä versio lauseesta ehdottaa yleistystä:
Todistamme ensin Mengerin alkuperäisen version tästä, ”paikallisen” version.
Teoreema 5.7.9 Jos $v$ ja $w$ ovat $G$:n ei-viereisiä kärkipisteitä, $\kappa_G(v,w)=p_G(v,w)$.
$$\bullet\quad\bullet\quad\bullet\quad\bullet$$
Palaamme lyhyesti 2-kytkentäisyyteen.Seuraavaa teoreemaa voidaan joskus käyttää induktiovaiheen antamiseen induktiotodisteessa.
Graafi, joka ei ole kytkeytynyt, koostuu kytkeytyneistä osista. Tätä muistuttavassa teoreemassa nähdään, että kytketyt graafit, jotka eivät ole2-kytkettyjä, rakentuvat 2-kytketyistä osagraafeista ja silloista.
Määritelmä 5.7.11 Lohko graafissa $G$ on maksimaalisesti indusoitunut osagraafi vähintään kahdessa kärjessä, jossa ei ole leikkauspistettä.
Kuten tavallista, maksimaalinen tarkoittaa tässä sitä, että indusoitua aligrafia $B$ ei voi tehdä suuremmaksi lisäämällä kärkipisteitä tai särmiä (säilyttäen halutun ominaisuuden, tässä tapauksessa ei leikkauspisteitä).Lohko on joko kaksiyhteinen indusoitu aligrafi tai yksittäinen särmä päätepisteineen. Lohkot ovathyödyllisiä suurelta osin tämän lauseen vuoksi:
Teoreema 5.7.12 $G$:n lohkot jakavat särmät.
Jos $G$:llä on yksi lohko, se on joko $K_2$ tai se on 2-liitännäinen, ja jokaisella 2-liitännäisellä graafilla on yksi lohko.
Teoreema 5.7.13 Jos $G$ on kytketty, mutta ei2-kytketty, niin jokainen kahdessa lohkossa oleva piste on $G$:n leikkauspiste.
Harjoituksia 5.7
Ex 5.7.1Esitellään, että yksinkertaisella graafilla $G$, jossa on $n\ge 2$ kärkipistettä, on vähintään $\ds {(n-1)(n-2)\over2}+1$ reunoja. Todista, että $G$ on kytketty.
Ex 5.7.3Esitellään, että $G$ on yksinkertainen ja että sen asteluku on $d_1\le d_2\le\cdots\le d_n$, ja kun $k\le n-d_n-1$, $d_k\ge k$. Näytetään, että $G$ on yhtenäinen.
Ex 5.7.4 Muistetaan, että graafi on $k$-säännöllinen, jos kaikilla kärkipisteillä on aste $k$. Mikä on pienin kokonaisluku $k$, jolla tämä pitää paikkansa:
Jos $G$ on yksinkertainen, sillä on $n$ kärkipistettä, $m\ge k$ ja $G$ on $m$-säännöllinen, niin $G$ on kytketty.
(Tietenkin $k$ riippuu $n$:stä).)
Ex 5.7.6Löydä yksinkertainen graafi, jolla on $\kappa(G)
Huomaa, että leikkauspiste sisältyy vähintään kahteen lohkoon, joten kaikki lohko-leikkauspiste-graafin riippuvat kärjet ovat lohkoja. Näitä lohkoja kutsutaan loppulohkoiksi.
Ex 5.7.10Piirrä alla olevan graafin lohko-leikkauspiste-graafi.