Graf G jest hamiltonowsko-spójny, jeśli dla dowolnych wierzchołków \(u, v \in V(G)\) istnieje w G ścieżka Hamiltona o końcach \(u, v\). Udowodnij, że jeśli graf G o co najmniej 4 wierzchołkach jest hamiltonowsko-spójny, to \(|E(G)| \geq \lfloor (3|V(G)| + 1)/2 \rfloor\).

Rozwiązanie (link)

Graf spójny 3-regularny o indeksie chromatycznym 3 i taki, że usunięcie pewnych dwóch krawędzi \(e\) i \(e'\) go rozspójnia, nazwiemy ciekawym.

(a) Podaj przykład (wraz z uzasadnieniem) ciekawego grafu.

(b) Udowodnij, że w każdym 3-kolorowaniu krawędziowym ciekawego grafu krawędzie \(e\) i \(e'\) mają taki sam kolor.

Rozwiązanie (link)

Znajdź liczbę rozwiązań kongruencji \( x^2 - x \equiv 31\) (mod 3025) w zbiorze {0, 1, …, 3024} i podaj jedno z nich.