Improved Inequality between Zagreb Indices of Trees1

For a simple graph G with n vertices and m edges, let M1 and M2 denote the first and the second Zagreb index of G. The inequality M1/n ≤ M2/m in the case of trees has been proved first by Vukičevic ́ and Graovac [MATCH Commun. Math. Comput. Chem. 57 (2007), 587–590], and a new proof has been found recently by Andova, Cohen and Škrekovski [Ars Math. Contemp. 5 (2012), 73– 76]. Here we improve this inequality by showing that, if T is not a star, then nM2 −mM1 ≥ 2(n − 3) + (Δ − 1)(Δ − 2), where Δ is the maximum vertex degree in T.