The converse to the $(1,1)$-degeneracy characterization of subgraph query complexity

Let $H$ be a graph. A graph is $(1,1)$-degenerate if its vertices can be partitioned into induced subgraphs $T_1,\ldots,T_n$ that are trees and satisfy

$$|N(v)\cap \bigcup_{i=1}^{k-1}T_i|\leq 1$$

for every $k\in\{1,\ldots,n\}$ and every $v\in T_k$. A graph is $2$-degenerate if every subgraph has a vertex of degree at most $2$. Let $f(H,p)$ denote the subgraph query complexity, and write $b$ for the relevant query parameter.

Converse to the $(1,1)$-degeneracy characterization. If $H$ is a $2$-degenerate graph that is not $(1,1)$-degenerate, then

$$f(H,p)=b^{2-o(1)}.$$

The preceding theorem proves the upper bound $f(H,p)=O(b^{2-\varepsilon})$ for every $(1,1)$-degenerate graph and some $\varepsilon=\varepsilon(H)>0$. The conjecture asserts that failure of $(1,1)$-degeneracy forces essentially quadratic query complexity; its resolution remains open.