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 S z ( G ) and the Wiener index W ( G ) , and between the revised Szeged index S z ∗ ( G ) and the Wiener index for a connected graph G . They conjectured that for a connected nonbipartite graph G with n ≥ 5 vertices and girth g ≥ 5 , S z ( G ) − W ( G ) ≥ 2 n − 5 , and moreover, the bound is best possible when the graph is composed of a cycle C 5 on 5 vertices and a tree T on n − 4 vertices sharing a single vertex. They also conjectured that for a connected nonbipartite graph G with n ≥ 4 vertices, S z ∗ ( G ) − W ( G ) ≥ n 2 + 4 n − 6 4 , and moreover, the bound is best possible when the graph is composed of a cycle C 3 on 3 vertices and a tree T on n − 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.