Let $G$ be a connected simple graph on $n$ vertices and $m$ edges. Denote $N_{ i}^{ (j)}(G)$ the number of spanning subgraphs of $G$ having precisely $i$ edges and not more than $j$ connected components. The graph $G$ is \emph{ strong} if $N_{ i}^{ j}(G)\geq N_{ i}^{ j}(H)$ for each pair of integers $i\in \{ 0,1,\ldots,m\}$ and $j\in \{ 1,2,\ldots,n\}$ and each connected simple graph $H$ on $n$ vertices and $m$ edges. The graph $G$ is \emph{ Whitney-maximum} if for each connected simple graph $H$ on $n$ vertices and $m$ edges there exists a polynomial $P_H(x,y)$ with nonnegative coefficients such that $W_{ G}(x,y)-W_H(x,y)=(1-xy)P_H(x,y)$, where $W_G$ and $W_H$ stand for the Whitney polynomial of $G$ and $H$. In this work it is proved that a graph is strong if and only if it is Whitney-maximum. Consequently, the $0$-element conjecture proposed by Boesch [J.\ Graph Theory 10 (1986), 339--352] is true when restricted to graph classes in which Whitney-maximum graphs exist.
Categories: math.CO