Dowód Twierdzenia Mantela (Delta 5 (422) 2009, str 4-5)

Pisałem w Ekstremalne grafy Turana o artykule Pawła Naroskiego w Delcie 5 (422) 2009, str. 4-5, którego to artykułu centralnym punktem było twierdzenie Mantela (1906 lub 1907 rok):

TWIERDZENIE (Mantel)
Maksymalna liczba krawędzi grafu beztrójkątowego o n wierzchołkach wynosi

floor(n/2) ⋅ ceiling(n/2)

Podane maksimum uzyskuje graf n-wierzchołkowy, w którym wierzchołki są rozbite na zbiory rozłączne A B, takie że |A| = floor(n/2), |B| = ceiling(n/2) oraz krawędziami są wszystkie pary

{a b}, gdzie a ∈ A oraz b ∈ B,

i tylko takie pary.

Niech (V E) będzie dowolnym grafem beztrójkątowym, o |V| = n wierzchołkach. Pozostało dowieść o zbiorze krawędzi E, że |E| ≤ floor(n/2) ⋅ ceiling(n/2). W artykule Naroskiego użyta była indikcja po n, w ktorej od n-1 przechodziło się do n. Natomiast natura funkcji floor oraz ceiling podpowiada przejście od n-2 do n. Uzyskuje się niewielkie, ale zawsze uproszczenie:

Oczywiście twierdzenie zachodzi dla n = 0 lub 1 wierzchołka. Niech teraz n > 1, oraz załóżmy (indukcja), że twierdzenie zachodzi dla n-2 wierzchołków. Jeżeli |E| = 0 to twierdzenie zachodzi. W przeciwnym wypadku ustalmy dowolną parę wierzchołków a b, połączonych krawędzią. Dowolny inny wierzchołek x połączony jest z co najwyżej z jednym z wierzchołków a b (by nie tworzyć trójkąta), tak że z wierzchołków a b wychodzi do pozostalych co najwyżej n-2 krawędzi, oraz jedna łączy a b, czyli w sumie wychodzi ich n-1. Pozostałe n-2 wierzchołki rozpinają podgraf beztrójkątny, mający wierzchołków co najwyżej

floor((n-2)/2) ⋅ ceiling((n-2)/2) = (floor(n/2) - 1) ⋅ (ceiling(n/2) - 1)

= floor(n/2) ⋅ ceiling(n/2) - (floor(n/2) + ceiling(n/2)) + 1

= floor(n/2) ⋅ ceiling(n/2) - n + 1

a cały graf ma ich o co najwyżej n-1 wiecej, czyli co najwyżej floor(n/2) ⋅ ceiling(n/2). KONIEC DOWODU

UWAGA 0: dowód byłby znacznie krótszy, gdybym zamiast terminu wierzchołek używał węzeł.

UWAGA 1: (poprzednia była li tylko żartem). W literaturze zamiast floor(n/2) ⋅ ceiling(n/2) występuje floor(n²/4). Oczywiście

floor(n²/4) = floor(n/2) ⋅ ceiling(n/2)

(wolę swoją wersję, bo pokazuje faktoryzację). Rachunki indukcyjne można było wykonać w formie standardowej z jeszcze większą łatwością :

floor((n-2)²/4) = floor(n²/4 - n + 1)

= floor(n²/4) - n + 1