Nice problem. We claim that the answer is $\boxed{n}$ if $n$ is even and $\boxed{n+1}$ if $n$ is odd. By shifting and scaling we can assume that the vertices of $\mathcal{P}$ are the $n^{th}$ roots of unity on complex plane. We first note that $f$ has the same sign on $\mathbb{R}^2$. This is because $\mathbb{R}^2 \setminus \mathcal{P}$ is connected and $f$ takes non-zero values, so $f$ must be positive everywhere or negative everywhere. WLOG $f \geq 0$. Clearly this implies degree of $f$ is even. Hence vertices $\mathcal{P}$ are local minima for $f$, and hence $\nabla f=0$ at $\mathcal{P}$. Now let $g(z)=f \left(\frac{z+\frac{1}{z}}{2}, \frac{z-\frac{1}{z}}{2i}\right)$. Clearly $g(z)=f(x,y)$ whenever $z=x+iy$ and $|z|=1$. Further, if $d= \deg(f)$, then $h(z)=z^dg(z)$ is a polynomial with degree at most $2d$. Hence $z^n-1 \mid h(z)$. Now, by chain rule, $$g'(z)=-\frac{1}{2z^2} \cdot \frac{\partial f}{\partial x} \left(\frac{z+\frac{1}{z}}{2}, \frac{z-\frac{1}{z}}{2i}\right) + \frac{1}{2iz^2} \cdot \frac{\partial f}{\partial y} \left(\frac{z+\frac{1}{z}}{2}, \frac{z-\frac{1}{z}}{2i}\right).$$Since gradient of $f$ vanishes, both the partial derivatives vanish on $\mathcal{P}$, and so $g'(z)$ vanishes at the $n^{th}$ roots of unity. Hence the $n^{th}$ roots of unity are also zeros of $h'(z)=dz^{d-1}g(z)+z^dg'(z)$, so $z^n-1 \mid h'(z)$, which implies $(z^n-1)^2 \mid h(z)$. Hence $2d \geq \deg(h) \geq 2n$, so $d \geq n$. Since $d$ is even, if $n$ odd we must have $d \geq n+1$. Now we give a construction. Let $z=x+iy$ and $\overline{z}=x-iy$. For $n$ odd, consider the polynomial $|z^{\frac{n+1}{2}}- (\overline{z})^{\frac{n-1}{2}}|^2$. This polynomial has degree $n+1$, and is $0$ iff $z^{\frac{n+1}{2}}=(\overline{z})^{\frac{n-1}{2}}$. Taking absolute values, this is possible only if $|z|=1$, and replacing $\overline{z}$ by $\frac{1}{z}$, this is possible iff $z^n=1$, as required. For $n$ even (now $n \geq 4$), consider $|z^{\frac{n}{2}}- (\overline{z})^{\frac{n}{2}}|^2+|z\overline{z}-1|^2$. This has degree $n$ (since $n \geq 4$), and is $0$ iff $z^{\frac{n}{2}}=(\overline{z})^{\frac{n}{2}}$ and $z \overline{z}=1$. From the latter, we get only if $|z|=1$, and replacing $\overline{z}$ by $\frac{1}{z}$ in the former, we again get iff $z^n=1$, as required.

Very Nice. Solved with Bhavya. Let $v(n)$ denote the smallest possible degree of a regular polygon. We claim that $$ v(n) = \begin{cases} n & n\equiv0\pmod 2 \\ n+1 & n\equiv 1\pmod 2 \end{cases} $$Bound: WLOG assume that the vertices are $n^{\text{th}}$ roots of unity. Claim 1: The degree of $f$ is even.

Let $g(z)=f\left(\frac{z-\frac{1}{z}}{2},\frac{z+\frac{1}{z}}{2i}\right)$ for $z=x+iy$, as $\frac{z-\frac{1}{z}}{2} = x$ and $\frac{z+\frac{1}{z}}{2i}=y$ therefore $g(z)=f(x,y)$, now define $h(z)=z^{v(n)} \cdot g(z)$, calculate gradient of $f$ (and the derivative of $g(z)$) using multi var chain rule, now noting that the vertices of $P$ are global minima, the gradient vanishes, so does the both partial derivatives, so $g'$ vanishes on $n^{th}$ roots of unity, therefore roots of unity are zeroes of $h'(z)$ as well by product rule, so $(z^n-1)^2 \mid h(z)$ which implies $v(n) \geq n$. Construction: Denote $z=x+iy$ and $z' = x-iy$, then consider the construction: $$ \text{Construction} = \begin{cases} |z^{\frac{n+1}{2}}- {z'}^{\frac{n-1}{2}}|^2+|zz'-1|^2& n\equiv1\pmod 2 \\ |z^{\frac{n}{2}}-z'^{\frac{n}{2}}|^2+|zz'-1|^2& n\equiv 0\pmod 2 \end{cases} $$which clearly work. Remark: We show an alternate elementary way of getting the bound after Claim 1, let $g(t)=f(\frac{1-t^2}{1+t^2}, \frac{2t}{1+t^2})$ and $h = g(t)(1+t^2)^{v(n)}$, observe $t^n-1 \mid g(t)$, assume if a root of $t^n-1$ is not a double root in $h$ then the sign of $f$ flips around that root, contradiction! hence by same degree counting arguement we conclude our proof. @Supercali, does not your construction for $n$ odd fail as $z=0$ also satisfies the equation?

Can someone check this idea? Apply a linear transformation so that the polygon has center the origin, radius 1 and all x coordinates of vertices are different. Once again we easily get that the polynomial is positive everywhere except the roots. Now consider w(x) = f(x, sqrt(1 - x^2))f(x, -sqrt(1 - x^2)). This is a polynomial in x, which is positive everywhere hence every real root is a double root. Since all x coordinates of the n-gon are root, we easily get that degree(f(x, y)) >= n.