Disconnectedness of H-free graphs adjacency structure

Problem 22 · arXiv:2506.08810

arXiv Problem high confidence— first stated 2025-09-01

Authors: Marthe Bonamy, Carla Groenland, Tom Johnston, Natasha Morrison, Alex Scott

Status open high confidence

Problem 22 from arXiv:2506.08810 asks for which finite graphs H the flip graph G_{H,n} (whose vertices are H-free graphs on [n] and whose edges connect graphs differing by exactly one edge) is disconnected for all sufficiently large n. The paper itself establishes that G_{P_4,n} is connected for all n≥1, ruling out universal disconnectedness. No follow-up paper addressing this problem was found in the indexed literature as of May 2026.

Reviewer notes. No follow-up work found. Semantic Scholar returns zero citations for arXiv:2506.08810 as of May 2026. The paper appeared in the Canadian Journal of Mathematics. The problem is recent (posted June 2025) and is a weaker relaxation of H-induced-saturation: an H-induced-saturated graph on n vertices corresponds to an isolated vertex in G_{H,n}, so disconnectedness of G_{H,n} is strictly weaker. The only known case mentioned in the paper is that G_{P_4,n} is connected for all n≥1.

Auto-reviewed 2026-05-14 with claude-sonnet-4-6 (web search enabled).

Problem. For a finite graph $H$ and integer $n$, let $G_{H,n}$ denote the graph with the $H$-free graphs on vertex set $[n]$ as vertices, and with an edge between $G,G^{\prime}\in V(G_{H,n})$ if and only if $|E(G)\triangle E(G^{\prime})|=1$. For which $H$ is $G_{H,n}$ disconnected for all sufficiently large $n$?

Context

An $H$-induced-saturated graph on $n$ vertices corresponds to an isolated vertex in $G_{H,n}$; disconnectedness is a weaker but potentially more tractable property. The authors note that $G_{P_4,n}$ is connected for all $n\geq 1$, so disconnectedness is not universal.

Source paper

Infinite induced-saturated graphs
Marthe Bonamy, Carla Groenland, Tom Johnston, Natasha Morrison, Alex Scott · 2025-09-01
https://arxiv.org/abs/2506.08810