Dowiedź tw o liczbie krawędzi:
Założenie:
\(\displaystyle{ \left| E\right| \ge \binom{n-1}{2} + 2}\)
Teza: graf G jest hamiltonowski
Dowód: ??
Obczytałem dowód na wkipedii i jakoś nie mogę tego zaczaić.
Dlaczego bierzemy sobie taki graf? (link w spoilerze, bo nie wiem czy można dawać linki)
Dlaczego potem usuwamy dwa wierzchołki? Prosiłbym o jakieś łopatologczne wyjaśnienie.
Ukryta treść: