Mam do rozwiązania dwa zadania dotyczące grafów i proszę o podpowiedź, wskazówkę od czego zacząć, jak ugryźć ten problem.
1.
Udowodnić, że dla grafów spójnych zachodzi nierówność \(\displaystyle{ s(G) \delta(G) < 3n}\), gdzie \(\displaystyle{ s(G)}\) jest średnicą grafu \(\displaystyle{ G}\), \(\displaystyle{ \delta(G)}\) najmniejszym
stopniem wierzchołka grafu \(\displaystyle{ G}\), a \(\displaystyle{ n}\) to liczba wierzchołków grafu \(\displaystyle{ G}\).
2.
Udowodnić, że graf \(\displaystyle{ G}\) dla którego zachodzi równość \(\displaystyle{ g(G)=2s(G) + 1}\) jest regularny, gdzie \(\displaystyle{ s(G)}\) jest średnicą, a \(\displaystyle{ g(G)}\) talią grafu, t.j. długością najkrótszego cyklu. Podać przykłady takich grafów.