August 2026

Quadratically Large Regular Graphs Without Internal Partitions

Ban and Linial conjectured that every 2k-regular graph with at least 4k vertices has an internal partition. This paper gives counterexamples whose size grows quadratically with k.

Read PDF

The k = 5 construction: an independent set W, five adjacent twin pairs, and the clique C. Every vertex in W connects to every twin-pair vertex, and each pair connects to three consecutive vertices of C.

Abstract

An internal partition of a graph is a nontrivial bipartition in which each vertex has at least as many neighbors in its own part as in the other part. In Internal Partitions of Regular Graphs (2016), Ban and Linial proposed in Conjecture 4 that every $2 k$ ‑regular graph on at least $4 k$ vertices has an internal partition. We disprove Conjecture 4 at its proposed threshold. For every odd integer $k \geq 5$ , we construct a $2 k$ ‑regular graph on exactly $(\binom{k + 2}{2})$ vertices with no internal partition. For every even integer $k \geq 8$ , we construct a $2 k$ ‑regular graph on exactly $(\binom{k + 1}{2}) + 2$ vertices with no internal partition. Both constructions also have connected complements. In fact, for each graph, every red-blue coloring in which each vertex has at least $k$ neighbors of its own color is monochromatic.