The Nordhaus-Gaddum upper-bound conjecture for the Cheeger constant

About 8 years old · traced to 2018

Let $G$ be a graph, let $G^c$ be its complement, and let $h(G)$ denote the Cheeger constant of $G$ . Write $S_n$ for the star graph on $n$ vertices, and let $K_3\vee E_{n-3}$ denote the join of the complete graph on three vertices and the edgeless graph on $n-3$ vertices.

Cheeger-constant Nordhaus-Gaddum conjecture. If $G\neq S_n$ , then

\max\{h(G),h(G^c)\}\leq h(K_3\vee E_{n-3}).

The conjecture is motivated by computational and structural comparisons among graph families, but the supplied text gives no resolution or status evidence beyond presenting it as a conjecture.

References

Primary source

Mark Kempton, Xavier Zaitzeff and Sibi Muthuprakash, “Nordhaus-Gaddum upper bounds for graph connectivity parameters”, arXiv:2606.12751 (2026).

Additional references

4 papers in this index state this conjecture (2018–2026). The statement above is taken from the most recent of them; the others are arXiv:2206.03723, arXiv:1808.05576, arXiv:1807.06436.

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed solved

A reader-submitted calculation claims the conjecture is false on seven vertices, but no independent verification was found.

Kempton, Zaitzeff, and Muthuprakash state this as Conjecture 1: excluding the star, the larger Cheeger constant of a graph and its complement should not exceed that of the proposed extremal graph. Their paper presents computational and structural motivation but no resolution.

Community submission (unverified), August 23, 2026

A submitted calculation claims a counterexample at seven vertices within the generalized-star family, taking $G=K_4\vee E_3$ . It reports an exhaustive cut-type computation yielding $h(G)=5/8$ and asserts that this exceeds the conjectured benchmark $h(K_3\vee E_4)$ . The argument is not independently verified.

Current status (as of August 2026): The conjecture has an unverified claimed counterexample at $n=7$ ; no independently confirmed proof or disproof is recorded.

Sources

arxiv.org

CounterexampleThis solution needs a summarySee full solutionHide full solution

A seven-vertex generalized-star counterexample

Conjecture 1 of Kempton, Zaitzeff, and Muthuprakash, Nordhaus–Gaddum upper bounds for graph connectivity parameters, asserts that every graph $G\neq S_n$ satisfies

\max\bigl\{h(G),h(G^c)\bigr\} \leq h\bigl(K_3\vee E_{n-3}\bigr), \tag{1}

where

h(F)=\min_{\varnothing\neq X\subsetneq V(F)} \frac{|\partial_F X|} {\min\{\operatorname{vol}_F(X), \operatorname{vol}_F(V(F)\setminus X)\}}. \tag{2}

The assertion already fails within the generalized-star family discussed in the paper.

Cut formula for generalized stars

Let

F_{r,s}=K_r\vee E_s, \qquad r+s=7,

and write $C$ and $I$ for its clique and independent-set parts. For any vertex subset $X$ , put

a=|X\cap C|, \qquad b=|X\cap I|.

The clique vertices have degree $6$ , and the independent-set vertices have degree $r$ . Consequently,

\begin{aligned} |\partial X| &=a(r-a)+a(s-b)+(r-a)b,\\ \operatorname{vol}(X) &=6a+rb,\\ \operatorname{vol}(V\setminus X) &=6(r-a)+r(s-b). \end{aligned} \tag{3}

The cut ratio is unchanged when $(a,b)$ is replaced by $(r-a,s-b)$ . It therefore suffices to list one representative from each complementary pair of nonempty proper cut types.

The counterexample

Take

G=F_{4,3}=K_4\vee E_3.

Formula (3) gives the following complete list, where $m(X)$ denotes the smaller of the two volumes:

\begin{array}{c|c|c|c|c} a&b&|\partial X|&m(X)&|\partial X|/m(X)\\ \hline 0&1&4&4&1\\ 0&2&8&8&1\\ 0&3&12&12&1\\ 1&0&6&6&1\\ 1&1&8&10&4/5\\ 1&2&10&14&5/7\\ 1&3&12&18&2/3\\ 2&0&10&12&5/6\\ 2&1&10&16&5/8 \end{array}

Hence

h(G)=\frac58. \tag{4}

On the other hand, the proposed seven-vertex extremal graph is

H=F_{3,4}=K_3\vee E_4.

Its complete list of complementary cut types is

\begin{array}{c|c|c|c|c} a&b&|\partial X|&m(X)&|\partial X|/m(X)\\ \hline 0&1&3&3&1\\ 0&2&6&6&1\\ 0&3&9&9&1\\ 0&4&12&12&1\\ 1&0&6&6&1\\ 1&1&7&9&7/9\\ 1&2&8&12&2/3\\ 1&3&9&15&3/5\\ 1&4&10&12&5/6 \end{array}

Therefore

h(H)=\frac35. \tag{5}

The graph $G$ is neither a star nor a complete graph. Its complement is

G^c=E_4\sqcup K_3,

which is disconnected, so $h(G^c)=0$ . Combining (4) and (5),

\boxed{ \max\bigl\{h(G),h(G^c)\bigr\} =\frac58 >\frac35 =h\bigl(K_3\vee E_4\bigr). }

Thus the conjectured bound is false. In particular, the proposed extremizer is not maximal even among seven-vertex generalized stars. The disconnected complement is permitted by the conjecture as stated; indeed, the proposed extremizer itself has disconnected complement.