Let $a_0<...<a_n$ be the x-coordinates of the vertices (clearly symmetric vertices wrt the x-axia have the same coordinate), and let $x_{2i-1},x_{2i}\in(a_{i-1},a_i)$ be the (or some of the) X coordinates of the various sides (and say $x_{2i-1}<x_{2i}$). Since $sgn(P(x_{2i-1})=-sgn(P(x_{2i}))$, it follows that there exists a $y_i\in(x_{2i-1},x_{2i})$ such that $P(y_i)=0$. Therefore, $P$ has at least $n$ solutions, and is at least of degree $n$. In fact, by taking $P(x)=C(x-y_1)\cdots (x-y_n)$ with $y_i\in(a_{i-1},a_i)$, with $C$ a big enough constant (so that the graph actually intersects the sides at least once), it is straightforward enough to see that we are done, and the minimal $d$ is $n$.

Nice look and a cute one !

Firstly , one can suppose that one of this polygon's largest diagonals lies on the $x$-axis. Now we will show that if the graph of polynomial $P(x)$ intersects all sides of this polygon , then $deg(P(x)) \ge n$. Suppose that $x_1<x_2<...<x_{2n}$ be the length of these $2n$ intersection points. Now one can see that no three consecutive intersection points whit lengths $x_{i-1} , x_i , x_{i+1}$ belongs to the sides $l_1 , l_2 , l_3$ on the same side of this polygon's mean diagonal ( which lies on $x$-axis ). Assume otherwise , then suppose that $l_2'$ be the reflection of $l_2$ with respect to mean diagonal , so for each point $P \in l_2'$ , $ x_{i-1}<x_P<x_{i+1}$ and as the result , there is no intersection point on the side $l_2'$ , which is a contradiction. Also whit the same reason , points $x_1 , x_2$ and $x_{2n-1} , x_{2n}$ are located on different sides of the $x$-axis. So by pigeonhole principle , there is at least $n$ numbers $i \le 2n$ so that $x_i$ and $x_{i+1}$ are located on different sides of the $x$-axis and for such $i$ by Rolle's theorem , $P(x)$ has a root in interval $(x_i , x_{i+1})$ and as the result , $P(x)$ has at least $n$ distinct real roots and $deg(P(x)) \ge n$. Now let $l_1 , l_2 , ... l_{n+1}$ be vertical lines such that $l_i$ passes trough vertexes $A_i$ and $A_{2n-i+2}$ of the polygon. then place points $P_1 , ... , P_{n+1}$ on these lines such that for each odd number $i$ , we have $y_{P_i}>y_{A_i} , y_{A_{2n-i+2}}$ and $y_{P_{i+1}}<y_{A_{i+1}} , y_{A_{2n-i+1}}$. So there is a unique polynomial $P(x)$ of degree $n$ passes trough these $n+1$ points and again by Rolle's theorem , this graph will intersect all sides of the polygon. So the answer is $n$ and we're done.