A New Proof of the Szeged-Wiener Theorem


H. Khodashenas, M. J. Nadjafi-Arani, A. R. Ashrafi, I. Gutman




The Wiener index $W(G)$ is the sum of distances between all pairs of vertices of a connected graph $G$. For an edge $e$ of $G$, connecting the vertices $u$ and $v$, the set of vertices lying closer to $u$ than to $v$ is denoted by $N_e(u)$. The Szeged index, $Sz(G)$, is the sum of products $|N_u(e)| \times |N_v(e)|$ over all edges of $G$. A block graph is a graph whose every block is a clique. The Szeged-Wiener theorem states that $Sz(G) = W(G)$ holds if and only if $G$ is a block graph. A new proof of this theorem if offered, by means of which some properties of block graphs could be established.