The (revised) Szeged index and the Wiener index of a nonbipartite graph

Hansen et al. used the computer program AutoGraphiX to study the differences between the Szeged index Sz(G)Sz(G) and the Wiener index W(G)W(G), and between the revised Szeged index Sz∗(G)Sz∗(G) and the Wiener index for a connected graph GG. They conjectured that for a connected nonbipartite graph GG with n≥5n≥5 vertices and girth g≥5g≥5, Sz(G)−W(G)≥2n−5Sz(G)−W(G)≥2n−5, and moreover, the bound is best possible when the graph is composed of a cycle C5C5 on 55 vertices and a tree TT on n−4n−4 vertices sharing a single vertex. They also conjectured that for a connected nonbipartite graph GG with n≥4n≥4 vertices, Sz∗(G)−W(G)≥n2+4n−64, and moreover, the bound is best possible when the graph is composed of a cycle C3C3 on 33 vertices and a tree TT on n−2n−2 vertices sharing a single vertex. In this paper, we not only give confirmative proofs to these two conjectures but also characterize those graphs that achieve the two lower bounds.