Counterexamples to a Nordhaus-Gaddum conjecture for the Cheeger constant

Kempton, Zaitzeff and Muthuprakash (arXiv:2606.12751v1, Conjecture 1) conjectured that every graph G other than the star S_n satisfies max{h(G), h(Gc)} <= h(K_3 v E_{n-3}), where h is the Cheeger constant (minimum over vertex subsets X of the number of edges leaving X divided by the smaller of the volumes of X and its complement, 0 for disconnected graphs). This note shows that the complete graph K_n violates the bound for n = 5, 7, 9 and 13: h(K_5) = 3/4 > 5/7, h(K_7) = 2/3 > 3/5, h(K_9) = 5/8 > 3/5 and h(K_13) = 7/12 > 19/33, while its complement has h = 0. Among 4 <= n <= 200 these are the only n where K_n violates the bound. The kite K_9 plus a pendant edge violates it at n = 10 (h = 10/17 > 7/12), and an exhaustive search over all graphs on at most 9 vertices finds five further violators on 7 and 9 vertices (complete graphs minus a few edges). A standard-library Python script checks all values in exact rational arithmetic. Searches and verification were carried out with Claude (Anthropic) under the direction of Kerem Özdemir.