(a) Let $p(X, Y)$ be such a polynomial. There are two possible cases:

Case 1. If $p(1, Y)=p(2, Y)=p(3, Y)=p(4, Y)=0$. In this case
$$(X-1)(X-2)(X-3)(X-4)$$
is a factor of $p(X, Y)$ and therefore $\deg p(X, Y) \geq 4$.

Case 2. If there exists $a_{0} \in \{1,2,3,4\}$ such that $p\left(a_{0}, Y\right) \neq 0$. Because $p\left(a_{0}, b\right)=0$ for $b \in \{1,2,3,4\} \setminus \{a_{0}\}$, the nonzero polynomial $p\left(a_{0}, Y\right)$ has 3 different roots and therefore $\deg p(X, Y) \geq \deg p\left(a_{0}, Y\right) \geq 3$.

Hence $\deg p(X, Y) \geq 3$.

To construct such a polynomial of degree 3, consider, as shown in the figure, the line of equation $x+y-5=0$ and the circle of equation $\left(x-\frac{5}{2}\right)^{2}+\left(y-\frac{5}{2}\right)^{2}-\frac{5}{2}=0$.

The graph obtained by union of this line and this circle passes by all the points of $S$. Therefore, the polynomial
$$p_{0}(X, Y)=(X+Y-5)\left(X^{2}+Y^{2}-5 X-5 Y+10\right)$$
satisfies the condition $p_{0}(a, b)=0$ for all $(a, b) \in S$ and is of degree 3. Hence the minimal degree of such polynomials $p(X, Y)$ is 3.

(b) Let $p(X, Y)$ be a nonzero polynomial of degree 3 with integer coefficients such that $p(a, b)=0$ for every element $(a, b)$ in $S$. From (a), there exists $a_{0} \in \{1,2,3,4\}$ such that $p\left(a_{0}, Y\right) \neq 0$. Let $p_{0}(X, Y)=(X+Y-5)\left((2 X-5)^{2}+(2 Y-5)^{2}-10\right)$ and define the polynomial
$$q(X, Y)=p_{0}\left(a_{0}, a_{0}\right) p(X, Y)-p\left(a_{0}, a_{0}\right) p_{0}(X, Y).$$
Polynomial $q(X, Y)$ is of degree at most 3. But polynomial $q\left(a_{0}, Y\right)$ has at least $1,2,3,4$ as roots. Therefore $q\left(a_{0}, Y\right)=0$, which means that $q(X, Y)=\left(X-a_{0}\right) q_{1}(X, Y)$ for some polynomial $q_{1}(X, Y)$ of degree at most 2. But for any $a \in \{1,2,3,4\} \setminus \{a_{0}\}, q_{1}(a, Y)$ has at least 3 roots, which implies that $q_{1}(a, Y)=0$. Hence $(X-1)(X-2)(X-3)(X-4)$ divides $q(X, Y)$ of degree 3. Therefore $q(X, Y)=0$. Because $p_{0}(X, Y)$ is a unitary polynomial, we deduce that
$$p(X, Y)=k p_{0}(X, Y), \quad \text{ for some } k \in \mathbb{Z}.$$