Iloczynem kartezjańskim grafów \(G_1 = \langle V_1, E_1\rangle\) i \(G_2 = \langle V_2, E_2\rangle\) nazywamy graf \(G_1\otimes G_2 = \langle V_1\times V_2, E\rangle\), gdzie
\[\{\langle v_1,v_2\rangle,\langle w_1,w_2\rangle\} \in E \Leftrightarrow (\{v_1,w_1\} \in E_1 \wedge \{v_2,w_2\} \in E_2)\ .\]
Udowodnij, że graf \(G_1\otimes G_2\) jest spójny wtedy i tylko wtedy, gdy obydwa grafy \(G_1\) i \(G_2\) są spójne i przynajmniej jeden z nich zawiera cykl nieparzystej długości.
Oblicz \(7^{8^9} \bmod 100\).
Udowodnij uogólnione Chińskie Twierdzenie o Resztach: Niech \(m_1,m_2>0\) niekoniecznie względnie pierwsze, \(m = \mbox{NWW}(m_1,m_2)\). Wtedy dla dowolnych \(u_1,u_2\geq 0\) istnieje dokładnie jedno u takie, że \( 0\leq u < m\) oraz \(u \equiv u_i (\mbox{mod } m_i)\) dla i=1,2, o ile \(u_1\equiv u_2 (\mbox{mod NWD}(m_1, m_2))\), a jeśli ten ostatni warunek nie jest spełniony, to takie u nie istnieje.