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 \(E_{\max}\) Kanten.
$$E_{\max}(|V(G)|=1) = 0$$$$E_{\max}(|V(G)|=2) = 1$$$$E_{\max}(|V(G)|=3) = 3$$$$E_{\max}(|V(G)|=n) = E_{\max}(|V(G)|=n-1) + n$$ $$E_{\max}(|V(G)|=n) = \frac{n}{2}(n-1)$$
Man muss also von einem Graphen mit \(E_{\max}\) 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 \(E_{\text{krit.}}\) der verbleibenden Kanten ist dann
$$E_{\text{krit.}} = \frac12 \left( |V(G)| - 1 \right) \left( |V(G)| - 2 \right) = \frac{ \left( |V(G)| - 1 \right)! }{\left( |V(G)| - 3 \right)! \cdot 2!} = \binom{ |V(G)| - 1}{2}$$
hat ein Graph \(G\) mehr Kanten als \(E_{\text{krit.}}\) so ist es zwangsläufig ein zusammen hängender.
