Matematyka.pl

\(\displaystyle{ Obserwacja 1:}\) Liczba krawędzi w grafie jest równa sumie stopni wierzchołków podzielonej przez \(\displaystyle{ 2}\). Skoro stopień każdego wierzchołka wynosi \(\displaystyle{ 5}\), to liczba wierzchołków musi być parzysta \(\displaystyle{ \left| V\right| =2n}\).

Uporządkujmy wierzchołki grafu według następującego porządku. Wierzchołek \(\displaystyle{ A}\) na poziomie \(\displaystyle{ 0}\), \(\displaystyle{ 5}\) wierzchołków sąsiadujących na poziomie \(\displaystyle{ 1}\), a pozostałe na poziomie \(\displaystyle{ 2}\). Wierzchołki na poziomie \(\displaystyle{ 1}\) muszą mieć dokładnie dwóch sąsiadów na tym poziomie. Dlatego liczba krawędzi między poziomem \(\displaystyle{ 1}\), a \(\displaystyle{ 2}\) wynosi \(\displaystyle{ 5 \cdot (5-3)=10}\). Na poziomie \(\displaystyle{ 2}\) znajduje się \(\displaystyle{ (2n-5-1)}\) wierzchołków, każdy z nich połączony z dokładnie dwoma na poziomie \(\displaystyle{ 1}\). Stąd wynika, że \(\displaystyle{ 10 = 2 \cdot (2n-6) = 4 \cdot (n-3) \Rightarrow n=3+ \frac{5}{2} }\). Nie istnieje zatem grupa osób opisywana w treści zadania.