Zagreb indices were reformulated in terms of the edge degrees instead of the vertex degrees. For a graph $G$, the first and second reformulated Zagreb indices are defined respectively as:$$EM_1(G)=\sum_{\varepsilon\in E(G)}d^2(\varepsilon), EM_2(G)=\sum_{\varepsilon,\varepsilon'\in E(G),\,\varepsilon\sim \varepsilon'}d(\varepsilon)\,d(\varepsilon'),$$ where $d(\varepsilon)$ and $d(\varepsilon')$ denote the degree of the edges $\varepsilon$ and $\varepsilon'$ respectively, and $\varepsilon\sim \varepsilon'$ means that the edges $\varepsilon$ and $\varepsilon'$ are adjacent. In this paper, we obtain sharp lower bounds on the first and second reformulated Zagreb indices with a given number of vertices and maximum degree. Furthermore, we will determine the extremal Trees that achieve these lower bounds.