The degree can't be $0$ since that will give us a constant polynomial, but we have $4$ different points to satisfy.
The points that we need to satisfy aren't co-linear either. For example, $\frac{p(1)-p(0)}{1-0} = -1 \quad\neq\quad 5 = \frac{p(2)-p(1)}{2-1}$
Let's try to fit a parabola.
Let $p(x) = ax^2 + bx + c$
Since $p(0) = 5$, we have that:
$$\begin{align}
a\cdot 0^2 + b\cdot 0 + c &= 5\\
c &= 5\\[1em]
\hline
\implies p(x) &= ax^2 + bx + 5
\end{align}$$
Also, $p(1) = 4$. Thus,
$$\begin{align}
a\cdot 1^2 + b\cdot 1 + 5 &= 4\\[1em]
a + b &= -1\tag{1}\label{1}
\end{align}$$
Finally, $p(2) = 9$. This gives us:
$$\begin{align}
a\cdot 2^2 + b\cdot 2 + 5 &= 9\\[1em]
4a + 2b &= 4\\[1em]
2a + b &= 2\tag{2}\label{2}
\end{align}$$
Using $\eqref{1} \,\&\, \eqref{2}$ we get:
$$\begin{array}{rrll}
+ (&2a + b &= 2 &)\\
- (&a + b &= -1 &)\\[1em]
\hline
\implies&a&=3\\
&b&=-4
\end{array}$$
So we have $p(x) = 3x^2 - 4x + 5$.
Testing it on our final point, we have that $p(3) = 3 \cdot 3^2 -4 \cdot 3 + 5 = 27 - 12 + 5 = 20$, which is equal to the given value of $p(3)$.
Hence, the minimum degree is $2$ and the polynomial is $p(x) = 3x^2 - 4x + 5$.
