2015 Drugie kolokwium

Zadanie 1

Znajdź liczbę drzew rozpinających grafu \(K_n\setminus \left\{e\right\}\) dla \(n\ge 3 \) gdzie \(e\in E(K_n)\) jest pewną ustaloną krawędzią.

Zadanie 2

Udowodnij że jeśli \(G\) jest grafem \(100\)-wierzchołkowym, w którym \(90\) wierzchołków ma stopień nie większy niż \(9\), to \(\chi(G)\le 10 \).

Zadanie 3

Udowodnij następującą cechę podzielności: liczba \(n\) jest podzielna przez \(73\) wtedy i tylko wtedy, gdy różnica liczby złożonej z czterech ostatnich cyfr zapisu dziesiętnego \(n\) i liczby złożonej z pozostałych cyfr jest podzielna przez \(73\) (np. liczba \(12345687\) jest podzielna przez \(73\), ponieważ różnica \(5687-1234=4453=73\cdot 61\) jest podzielna przez \(73\)).