Spójność grafu

[alto de aitana]

Graf prosty o 21 wierzchołkach. Dla dowolnej pary wierzchołków \(\displaystyle{ x, y}\) zachodzi warunek \(\displaystyle{ d(x)+d(y) \ge 20}\). Czy graf jest spójny?

[Mruczek]

Załóżmy, że nie jest spójny. To znaczy, że ma przynajmniej dwie spójne składowe. Któraś ze spójnych musi zawierać co najwyżej \(\displaystyle{ 10}\) wierzchołków. Jeżeli jest wśród nich spójna wielkości \(\displaystyle{ 1}\) to bierzemy wierzchołek z tej spójnej i dowolny inny (który ma co najwyżej \(\displaystyle{ 19}\) sąsiadów) - wtedy \(\displaystyle{ d(x) + d(y) \le 0 + 19 = 19}\), sprzeczność. Wpp. istnieje spójna, która ma więcej niż \(\displaystyle{ 1}\) i nie więcej niż \(\displaystyle{ 10}\) wierzchołków. Weźmy dowolne dwa wierzchołki z tej spójnej - wtedy \(\displaystyle{ d(x) + d(y) \le 9 + 9 = 18}\) - stopień każdego z tych wierzchołków nie może przekraczać wielkości spójnej minus \(\displaystyle{ 1}\), czyli \(\displaystyle{ 9}\), sprzeczność.

To znaczy, że jest spójny.

[alto de aitana]

Dlaczego, ktoras ze spojnych musi zawierac co najwyzej 10 wierzcholkow?

[miodzio1988]

Dlaczego, ktoras ze spojnych musi zawierac co najwyzej 10 wierzcholkow?

No bo masz \(\displaystyle{ 21}\) wierzchołków. Czyli jak jedna ma \(\displaystyle{ 15}\) wierzchołków to kolejna ma co najwyżej \(\displaystyle{ 10}\) itd.