The strengthened Szeged–Wiener lower bound for 2-connected graphs

About 10 years old · traced to 2016

Let $G$ be a $2$ -connected graph of order $n\ge 10$ . Let $K_n$ denote the complete graph, and let $K_n^2$ and $K_n^{n-2}$ be the graphs obtained from $K_{n-1}$ by adding one vertex adjacent to respectively $2$ or $n-2$ of the original vertices. Define $\eta(G)=\operatorname{Sz}(G)-W(G)$ . Strengthened Szeged–Wiener conjecture. If $G$ is not isomorphic to $K_n$ , $K_n^2$ , or $K_n^{n-2}$ , then

\eta(G)\ge 2n.

The conjecture is motivated by computer searches finding graphs with $\eta(G)<2n$ only up to order $9$ , with none on $10$ vertices. The source does not provide a proof or resolution, so the conjecture remains open.

References

Primary source

Marthe Bonamy, Martin Knor, Borut Lužar, Alexandre Pinlou and Riste Škrekovski, “On the difference between the Szeged and Wiener index”, arXiv:1602.05184 (2016).

Posted 1 month ago · edited 4 weeks ago

Progress summary

Refreshed 4 weeks ago

Open

A reader-submitted proof claims to settle the strengthened inequality, but it is incomplete and unverified, so the problem remains open.

Bonamy, Knor, Lužar, Pinlou, and Škrekovski formulated the conjecture in their 2016 work: apart from three exceptional graphs, every $2$ -connected graph with at least $10$ vertices should satisfy the strengthened lower bound.

Known results

Every $2$ -connected noncomplete graph of order $n$ satisfies $\eta(G)=\operatorname{Sz}(G)-W(G)\ge 2n-6$ .
Equality occurs exactly for $K_n^2$ and $K_n^{n-2}$ .
Excluding those two families gives $\eta(G)\ge 2n-5$ .
Exhaustive searches found examples with $\eta(G)<2n$ through order $9$ , but none at order $10$ .

Community submission (unverified)

On September 8, 2026, a submitted proof argued for the full conjecture using a minimal-counterexample argument, dominated-vertex reductions, block decomposition, induction, and a finite certificate. The submission is truncated and has not been independently checked.

Current status (as of September 2026): The $2n-6$ and $2n-5$ bounds are established, but the strengthened inequality for all $n\ge 10$ remains open because the submitted proof is unverified.

Sources

ProofI give a complete computer-assisted proof of the strengthened Szeged-Wiener conjecture of Bonamy, Knor, Lužar, Pinlou and Škrekovski. The proof combines their dominated-vertex reduction with two new exact extension bounds and a finite verification of the remaining low-order cases. In particular, every 2-connected graph

G

of order

n\ge 10

, other than

K_n,K_n^2,K_n^{n-2}

, satisfies

Sz(G)-W(G)\ge 2n

.See full solutionHide full solution

I prove the strengthened Szeged-Wiener conjecture. The complete proof and the exact finite certificate are attached; here I give the structure of the argument.

For a connected graph $G$, write

\eta(G)=Sz(G)-W(G).

The conjecture asserts that every 2-connected graph of order $n\ge 10$, except the three stated exceptional families, satisfies

\eta(G)\ge 2n.

The proof starts from Proposition 6 and Lemmas 7, 9, and 10 of Bonamy, Knor, Lužar, Pinlou and Škrekovski (2017).

Assume that $G$ is a counterexample of minimum order. By Lemma 10 there are distinct vertices $u,v$ such that the closed neighborhood of $u$ is contained in the closed neighborhood of $v$. Put

H=G-u.

If $H$ is complete, then $G$ belongs to the family $K_n^t$, and direct counting gives

\eta(K\_n^t)=2(t-1)(n-t-1).

Outside the two exceptional values of $t$, this is at least $2n$.

If $H$ is 2-connected, noncomplete, and nonexceptional, then the minimality of $G$ and Lemma 7 give

\eta(H)\ge 2(n-1), \qquad \eta(G)-\eta(H)\ge 2,

hence

\eta(G)\ge 2n.

The two exceptional 2-connected deletions require separate treatment. A complete classification of their possible dominated extensions, followed by direct Szeged-index counting, gives the two bounds

\eta(G)\ge 3n-10

and

\eta(G)\ge 4n-16,

respectively, unless $G$ itself is one of the exceptional graphs excluded in the conjecture. Both bounds imply the required inequality for $n\ge 10$.

It follows that, in a minimum counterexample, every dominated deletion must be non-2-connected. Lemma 9 then gives a block decomposition. For the corresponding 2-connected pieces, the required exact low-order lower bounds are

L(5)=10,\quad L(6)=8,\quad L(7)=11,\quad L(8)=14,\quad L(9)=17.

For larger pieces the induction hypothesis gives $L(s)\ge 2s$.

The good-edge argument from the proof of Theorem 4 of Bonamy et al. then yields

\eta(G)\ge 2n+(k-1)(k+4)+ \sum\_{i=1}^{k} d(s\_i),

where

d(5)=0,\quad d(6)=-4,\quad d(7)=-3,\quad d(8)=-2,\quad d(9)=-1,

and $d(s)\ge0$ for $s\ge10$.

This settles every case with at least three blocks, and every two-block case of order at least $12$. Only two finite block configurations remain. Their exact verification gives

n=10:\quad \min\eta=20,

and

n=11:\quad \min\eta=23&gt;22.

The remaining 2-connected part of the order-10 base case is reduced by two successive dominated-vertex extensions. The certificate checks

97\longrightarrow681\longrightarrow300311

labelled instances, without graph-isomorphism deduplication. The minimum value obtained at order 10 is $20$, so no counterexample occurs.

All finite computations use exact integer shortest-path distances and the defining formulas for the Wiener and Szeged indices; no floating-point calculation is used.

Thus every branch of a minimum counterexample is impossible. Therefore

Sz(G)-W(G)\ge2n

for every graph covered by the conjecture.

This proves the strengthened Szeged-Wiener conjecture.

The attached PDF contains the complete proofs of the exceptional-extension lemmas, the block reduction, and the finite reductions. The attached text file contains the reproducible exact certificate.

Reference: M. Bonamy, M. Knor, B. Lužar, A. Pinlou, R. Škrekovski, "On the difference between the Szeged and the Wiener index", Applied Mathematics and Computation 312 (2017), 202-213. DOI: 10.1016/j.amc.2017.05.047.

Szeged_Wiener_2026-09-08 .pdf131,108 bytesOpen
Preview text
Szeged_Wiener_Exact_Certificate_2026-09-08.txt66,010 bytesOpen