Matematyka.pl

Ile wierzchołków może mieć graf regularny stopnia \(\displaystyle{ > 2}\), który ma \(\displaystyle{ 2014}\) wierzchołków?

Z zadania wynika, że wierchołki w grafie są połączone wg zasady "każdy z każdym". W grafie regularnym jest \(\displaystyle{ \frac{n(n-1)}{2}}\) krawędzi. Zatem można napisać, że:

\(\displaystyle{ 2014 = \frac{n(n-1)}{2}}\)

Jednak jest taki problem, że delta równania kwadratowego, które powstaje:
\(\displaystyle{ n(n-1)=4028}\)

nie jest liczbą naturalną, a nie może być np. pół wierzchołka. Co może być źle?

2014?...

\(\displaystyle{ \frac{n(n-1)}{2}}\) krawędzi to jest w grafie pełnym (który, swoją drogą, też jest regularny, \(\displaystyle{ n-1}\)-regularny), ale w grafie regularnym, w którym każdy wierzchołek jest stopnia \(\displaystyle{ r}\), jest \(\displaystyle{ \frac{r \cdot n}{2}}\) krawędzi (każda krawędź łączy dwa wierzchołki, z każdego wierzchołka wychodzi \(\displaystyle{ r}\) krawędzi), więc musisz szukać takich \(\displaystyle{ r}\) oraz \(\displaystyle{ n}\), że zachodzi \(\displaystyle{ \frac{n \cdot r}{2} = 2014}\).