nierówność w grafie

[TrzyRazyCztery]

pokaż że dowolny graf \(\displaystyle{ G}\) zawierający conajmniej jedną krawędź posiada podgraf \(\displaystyle{ H}\) taki że \(\displaystyle{ \partial \left( H\right) \ge \frac{1}{2}d\left( H\right) \ge \frac{1}{2}d\left( G\right)}\) gdzie \(\displaystyle{ \partial (G)}\) to minimalny stopien wierzchołka w G a \(\displaystyle{ d\left( G\right)}\) to średni stopień wierzchołka w G

[Mruczek]

Wykonujemy w pętli następujący algorytm:
1. Jeżeli każdy wierzchołek ma w \(\displaystyle{ G}\) stopień nie mniejszy niż \(\displaystyle{ \frac{1}{2}d\left( G\right)}\), to \(\displaystyle{ H := G}\) i koniec algorytmu.
Jeżeli nie, to weźmy taki wierzchołek \(\displaystyle{ u \in V(G)}\), że \(\displaystyle{ deg(u) < \frac{1}{2}d\left( G\right)}\).
2. \(\displaystyle{ G' := G \setminus {u}}\) (usuwamy wierzchołek \(\displaystyle{ u}\) z \(\displaystyle{ G}\))
3. \(\displaystyle{ G := G'}\)

Pokażemy, niezmiennik \(\displaystyle{ d(\left G' \right) \ge d\left( G\right)}\):
\(\displaystyle{ deg(u) < \frac{d}{2}}\), więc po usunięciu \(\displaystyle{ u}\) suma stopni zmniejszy się o \(\displaystyle{ 2 deg(u)}\). Niech
\(\displaystyle{ S = \sum_{v \in V(G)}^{}deg(v)}\)
\(\displaystyle{ \frac{S}{|V(G)|} = d(G)}\), czyli \(\displaystyle{ S = d(G) \cdot |V(G)|}\).
\(\displaystyle{ d(G') = \frac{\sum_{v \in V(G')}deg(v)}{|V(G')|} = \frac{S - 2deg(u)}{|V(G)| - 1} \ge \frac{S - d(G)}{|V(G)| - 1} = \frac{d(G) \cdot |V(G)| - d(G)}{|V(G)| - 1} = d(G)}\)
Tak więc w każdym kroku algorytmu zachowany jest niezmiennik \(\displaystyle{ d\left( G'\right) \ge d\left( G\right)}\).

Jest jasne, że po zakończeniu algorytmu wszystkie wierzchołki grafu \(\displaystyle{ H}\) będą miały stopień nie mniejszy niż \(\displaystyle{ \frac{1}{2}d\left( H\right)}\), czyli \(\displaystyle{ \partial \left( H\right) \ge \frac{1}{2}d\left( H\right)}\). Z powyższego niezmiennika wynika druga nierówność: \(\displaystyle{ \frac{1}{2}d\left( H\right) \ge \frac{1}{2}d\left( G\right)}\).
Teraz wystarczy jeszcze pokazać, że algorytm nie usunie wszystkich wierzchołków z grafu. Dowód nie wprost. To znaczy, że algorytm musiał w ostatnim kroku usunąć ostatni wierzchołek z grafu, w tym momencie średni stopień byłby równy \(\displaystyle{ 0}\), ale na początku \(\displaystyle{ d\left( G\right) > 0}\), bo \(\displaystyle{ E(G) > 0}\) oraz w każdym kroku zachowany jest niezmiennik \(\displaystyle{ \frac{1}{2}d\left( G'\right) \ge \frac{1}{2}d\left( G\right) > 0}\), sprzeczność, cnd.