For any two integers $d,r \geq 1$, we show that there exists an edge ideal $I(G)$ such that the ${\rm reg}(R/I(G))$, the Castelnuovo-Mumford regularity of $R/I(G)$, is $r$, and $\deg h_{R/I(G)}(t)$, the degree of the $h$-polynomial of $R/I(G)$, is $d$. Additionally, if $G$ is a graph on $n$ vertices, we show that ${\rm reg}(R/I(G)) + \deg h_{R/I(G)}(t) \leq n$. This is joint work with T. Hibi and K. Matsuda.