turniej pilkarski

[kriegor]

\(\displaystyle{ 18}\) druzyn pilkarskich bierze udzial w turnieju
w pierwszej turze kazda z druzyn rozegrala \(\displaystyle{ 8}\) meczy
wykaz ze wsrod tych druzyn nie mozna znalezc trzech takich ktore nie rozegraly ze soba zadnego meczu

[sorcerer123]

mam taki pomysł, ale nie wiem, czy jest do końca dobry

Trzeba rozważyć graf \(\displaystyle{ G}\) o 18 wierzchołkach, w którym każdy wierzchołek jest stopnia 8. Trzeba pokazać, że taki graf ma co najwyżej dwie składowe.

Rozważmy graf \(\displaystyle{ G}\) o k składowych spójnych, w którym każdy wierzchołek ma stopień równy 8. W każdej składowej spójnej jest co najmniej 9 wierzchołków (wierzchołek i jego ośmiu sąsiadów nieleżących w innych składowych), czyli liczba wierzchołków w grafie spełnia nierówność

\(\displaystyle{ k \cdot 9 \le 18}\) // k składowych spójnych po 9 wierzchołków każda <= liczba wszystkich wierzchołków w grafie

\(\displaystyle{ k \le 2}\)

czyli nasz graf ma co najwyżej dwie składowe

Jeżeli można byłoby znaleźć trzy takie drużyny, które nie rozegrały ze sobą żadnego meczu, to graf miałby co najmniej trzy składowe spójne.