Finite deletion-induced saturation for every non-complete graph

Source abstract

A graph $G$ is deletion-induced-saturated for $H$ if $G$ has an edge, contains no induced copy of $H$, and deleting any edge of $G$ creates an induced copy of $H$. We prove, with finite certificate verification, that a finite graph $H$ admits such a finite graph $G$ if and only if $H$ is not complete. This resolves the deletion conjecture of Fan, Hajebi, Hajebi and Spirkl. The main step transfers suitable free amalgamations to finite extensions using a local lifting theorem of Auinger, Bitterlich and Otto. A second criterion treats edge addition by protecting specified nonedges and then taking a maximal induced-$H$-free completion. Structural results of Bonamy, Groenland, Johnston, Morrison and Scott reduce the remaining targets to dense templates and a finite hereditary class. Two uniform constructions in halved cubes handle the dense templates. The finite part is supported by exhaustive coverage certificates, structural certificates and explicit hosts, including a circulant graph on $30$ vertices.