A novel graph polynomial, termed as vertex degree polynomial, has been conceptualized, and its discriminating power has been investigated regarding its coefficients and the coefficients of its derivatives and their relations with the physical and chemical properties of molecules. Correlation coefficients ranging from 95% to 98% were obtained using the coefficients of the first and second derivatives of this new polynomial. We also show the relations between this new graph polynomial, and two oldest Zagreb indices, namely the first and second Zagreb indices. We calculate the vertex degree polynomial along with its roots for some important families of graphs like tadpole graph, windmill graph, firefly graph, Sierpinski sieve graph and Kragujevac trees. Finally, we use the vertex degree polynomial to calculate the first and second Zagreb indices for the Dyck-56 network and also for the chemical compound triangular benzenoid G[r]. Publisher's Version