Na ja - man kann sich z.B. fragen, wie viele Kanten ein einfacher ungerichteter Graph maximal haben kann und wieviele Kanten man davon mindestens wegnehmen muss, damit er nicht mehr zusammenhängend ist. Umgekehrt kann man dann sagen, dass ein Graph, der mehr Kanten hat, als diese oben beschriebene Anzahl, immer zusammenhängend sein muss.
Denk' mal selber nach und drücke nicht sofort auf den 'Spoiler'.
Wenn jeder Knoten mit jedem anderen über eine Kante verbunden ist, so hat der Graph Emax Kanten.
Emax(∣V(G)∣=1)=0Emax(∣V(G)∣=2)=1Emax(∣V(G)∣=3)=3Emax(∣V(G)∣=n)=Emax(∣V(G)∣=n−1)+n Emax(∣V(G)∣=n)=2n(n−1)
Man muss also von einem Graphen mit Emax Kanten mindestens ∣V(G)∣−1 Kanten entfernen - nämlich alle, die zu genau einem Knoten führen - um diesen einen Knoten zu isolieren. Die Anzahl Ekrit. der verbleibenden Kanten ist dann
Ekrit.=21(∣V(G)∣−1)(∣V(G)∣−2)=(∣V(G)∣−3)!⋅2!(∣V(G)∣−1)!=(2∣V(G)∣−1)
hat ein Graph G mehr Kanten als Ekrit. so ist es zwangsläufig ein zusammen hängender.