Graf i zbiór

[Polek]

Niech \(\displaystyle{ G=(V,E)}\) będzie grafem, którego zbiorem wierzchołków jest zbiór wszystkich 3-elementowych podzbiorów zbioru \(\displaystyle{ \{1,2,3,4,5,6,7\}}\). Krawędzie łączą te podzbiory, które nie mają wspólnych elementów. Czy jest to graf eulerowski?

Liczba 3-el. podzbiorów to \(\displaystyle{ \binom{7}{3}}\), ale jak wybrać podzbiory, które nie mają wspólnych elementów to nie mam pojęcia. Jakaś pomoc?

[Qń]

Wskazówka: wykaż, że stopień każdego wierzchołka to cztery.

Q.

[Polek]

Hmmm... Czyli każdy zbiór 3-elementowy nie ma wspólnych elementów z podzbiorami złożonymi z pozostałych 4-elementów? \(\displaystyle{ {4 \choose 3} = 4}\)?

[Qń]

Zgadza się. W połączeniu z warunkiem na eulerowskość grafu - to koniec.

Q.