A tau-critical graph with a large low-degree induced subgraph has a rooted stable-tooth comb

If $\delta >1$, then no nonempty graph can have a subset $X\subseteq V(G)$ with $\mathrm{\mid }X\mathrm{\mid }\ge \delta \mathrm{\mid }V(G)\mathrm{\mid }$, so the theorem is vacuous. Hence we may assume $\delta \le 1$. Choose ${\tau }_0\in (0,1\mathrm{/}2)$ so small that $\frac{2^{1-1\mathrm{/}{\tau }_0}}{\delta }+(ϵ+\frac{19}{20})(ϵ\delta {)}^{-{\tau }_0}<1$. Because $ϵ\delta <1\mathrm{/}20<1$, decreasing $\tau$ decreases both summands, so the same inequality holds for every $0<\tau \le {\tau }_0$.

By [L1], $\kappa (G)<\mathrm{\mid }V(G){\mathrm{\mid }}^{\tau }$. Since $\kappa (G)$ is a positive integer for every nonempty graph, it cannot equal $1$: otherwise [L2] would force $\alpha (G)=\omega (G)=1$, hence $\mathrm{\mid }V(G)\mathrm{\mid }=1$, contradicting $1<1^{\tau }$. Therefore $\kappa (G)\ge 2$, so $2<\mathrm{\mid }V(G){\mathrm{\mid }}^{\tau }$ and hence $\mathrm{\mid }V(G)\mathrm{\mid }>2^{1\mathrm{/}\tau }$.

Set $X_0:=X$. As long as $X_{i-1}\mathrm{\ne }\mathrm{\varnothing }$, choose a vertex $v_i\in X_{i-1}$ of maximum degree in $G[X_{i-1}]$, let $A_i:=N_{G[X_{i-1}]}(v_i)$, choose a stable set $C_i\subseteq A_i$ with $\mathrm{\mid }{C}_i\mathrm{\mid }\ge \mathrm{\mid }{A}_i{\mathrm{\mid }}^{\tau }\mathrm{/}\omega (G)$, and let $X_i$ be the set of vertices in $X_{i-1}\setminus \{v_i\}$ with no neighbour in $\{v_i\}\cup C_i$. This is possible because when $A_i\mathrm{\ne }\mathrm{\varnothing }$, the induced subgraph $G[A_i]$ is proper, so [L1] and [L2] give $\alpha (G[A_i])\ge \kappa (G[A_i])\mathrm{/}\omega (G)\ge \mathrm{\mid }{A}_i{\mathrm{\mid }}^{\tau }\mathrm{/}\omega (G)$. The process stops after finitely many steps because $v_i\mathrm{\notin }{X}_i$, so $\mathrm{\mid }{X}_i\mathrm{\mid }<\mathrm{\mid }{X}_{i-1}\mathrm{\mid }$ whenever $X_{i-1}\mathrm{\ne }\mathrm{\varnothing }$.

For $i<j$, the set $X_j$ is contained in $X_i$, so by construction there are no edges from $\{v_i\}\cup C_i$ to $X_j$. Hence $v_1,\dots ,v_s$ are pairwise nonadjacent, and $C_1\cup \cdots \cup C_s$ is stable. For each $i$, let $D_i$ be the set of vertices in $X_{i-1}\setminus (A_i\cup \{v_i\})$ that have a neighbour in $C_i$. Then $X=\{v_1,\dots ,v_s\}\bigsqcup A_1\bigsqcup \cdots \bigsqcup A_s\bigsqcup D_1\bigsqcup \cdots \bigsqcup D_s$, because every vertex removed when passing from $X_{i-1}$ to $X_i$ is either $v_i$, a neighbour of $v_i$, or a vertex outside $A_i\cup \{v_i\}$ with a neighbour in $C_i$.

Put $\gamma :=\delta \mathrm{/}(400ϵ)$. Fix $1\le i\le s$. If $A_i=\mathrm{\varnothing }$, then $C_i=\mathrm{\varnothing }$ and therefore $D_i=\mathrm{\varnothing }$, so certainly $\mathrm{\mid }{D}_i\mathrm{\mid }\le 19\sqrt{\mathrm{\mid }{A}_i\mathrm{\mid }\mathrm{\mid }X\mathrm{\mid }\mathrm{/}(400ϵ)}$. Assume now that $A_i\mathrm{\ne }\mathrm{\varnothing }$. Every vertex of $D_i$ has a neighbour in $C_i$ by definition, and every vertex of $C_i$ has at most $\mathrm{\mid }{A}_i\mathrm{\mid }$ neighbours in $D_i$ because $v_i$ has maximum degree in $G[X_{i-1}]$ and $\mathrm{\mid }{A}_i\mathrm{\mid }={\mathrm{deg}}_{G[X_{i-1}]}(v_i)$. Apply [L3] to the bipartite graph between $C_i$ and $D_i$ with $\mathrm{\Gamma }:=\gamma \mathrm{\mid }X\mathrm{\mid }\mathrm{/}\delta =\mathrm{\mid }X\mathrm{\mid }\mathrm{/}(400ϵ)$, $\mathrm{\Delta }:=\mathrm{\mid }{A}_i\mathrm{\mid }$, and $d:=1\mathrm{/}2$. If [L3] yields a $(t,\mathrm{\Gamma }{t}^{-2})$-comb $((a_j,B_j):1\le j\le t)$ in $(C_i,D_i)$, then the blocks lie in $X$, the teeth lie in the stable set $C_i$, and $v_i$ is adjacent to every tooth and anticomplete to every block. Thus [L4] gives a rooted stable-tooth comb in $G[X]$. Also $t\mathrm{\Gamma }{t}^{-2}\le \mathrm{\mid }X\mathrm{\mid }$ because the $t$ disjoint blocks lie in $X$, so $t\ge 1\mathrm{/}(400ϵ)$, and $\mathrm{\Gamma }{t}^{-2}=\mathrm{\mid }X\mathrm{\mid }\mathrm{/}(400ϵt^2)\ge \delta \mathrm{\mid }V(G)\mathrm{\mid }\mathrm{/}(400ϵt^2)$. Therefore the theorem is proved in this case. We may hence assume instead that $\mathrm{\mid }{D}_i\mathrm{\mid }\le \frac{3^{3\mathrm{/}2}}{3\mathrm{/}2-(3\mathrm{/}2{)}^{1\mathrm{/}2}}\sqrt{\mathrm{\mid }{A}_i\mathrm{\mid }\mathrm{\mid }X\mathrm{\mid }\mathrm{/}(400ϵ)}\le 19\sqrt{\mathrm{\mid }{A}_i\mathrm{\mid }\mathrm{\mid }X\mathrm{\mid }\mathrm{/}(400ϵ)}$. This bound now holds for every $1\le i\le s$.

Let $x_i:=\mathrm{\mid }{A}_i\mathrm{\mid }\mathrm{/}\mathrm{\mid }X\mathrm{\mid }$. Since $C_1\cup \cdots \cup C_s$ is stable by step 2.1, its size is at most $\alpha (G)$. On the other hand, step 1.3 and [L1] give $\mathrm{\mid }{C}_i\mathrm{\mid }\ge \mathrm{\mid }{A}_i{\mathrm{\mid }}^{\tau }\mathrm{/}\omega (G)=x_i^{\tau }\mathrm{\mid }X{\mathrm{\mid }}^{\tau }\mathrm{/}\omega (G)\ge (x_i\delta {)}^{\tau }\mathrm{\mid }V(G){\mathrm{\mid }}^{\tau }\mathrm{/}\omega (G)>(x_i\delta {)}^{\tau }\alpha (G)$. Summing over $i$ and dividing by $\alpha (G)$ yields ${\sum }_{i=1}^s{x}_i^{\tau }<{\delta }^{-\tau }$.

Since $v_1,\dots ,v_s$ are stable by step 2.1, we have $\frac{s}{\mathrm{\mid }X\mathrm{\mid }}\le \frac{\alpha (G)}{\mathrm{\mid }X\mathrm{\mid }}\le \frac{\kappa (G)}{\mathrm{\mid }X\mathrm{\mid }}<\frac{\mathrm{\mid }V(G){\mathrm{\mid }}^{\tau }}{\mathrm{\mid }X\mathrm{\mid }}\le \frac{\mathrm{\mid }V(G){\mathrm{\mid }}^{\tau -1}}{\delta }<\frac{2^{1-1\mathrm{/}\tau }}{\delta }$, where the last inequality uses step 1.2.

Because $X_{i-1}\subseteq X$ and $v_i$ has maximum degree in $G[X_{i-1}]$, we have $x_i=\mathrm{\mid }{A}_i\mathrm{\mid }\mathrm{/}\mathrm{\mid }X\mathrm{\mid }\le ϵ\delta \mathrm{\mid }V(G)\mathrm{\mid }\mathrm{/}\mathrm{\mid }X\mathrm{\mid }\le ϵ$. Hence ${\sum }_{i=1}^s{x}_i={\sum }_{i=1}^s{x}_i^{\tau }{x}_i^{1-\tau }\le {ϵ}^{1-\tau }{\sum }_{i=1}^s{x}_i^{\tau }\le ϵ(ϵ\delta {)}^{-\tau }$, and, because $\tau <1\mathrm{/}2$, ${\sum }_{i=1}^s{x}_i^{1\mathrm{/}2}={\sum }_{i=1}^s{x}_i^{\tau }{x}_i^{1\mathrm{/}2-\tau }\le {ϵ}^{1\mathrm{/}2-\tau }{\sum }_{i=1}^s{x}_i^{\tau }\le {ϵ}^{1\mathrm{/}2}(ϵ\delta {)}^{-\tau }$.

Divide the partition identity in step 2.1 by $\mathrm{\mid }X\mathrm{\mid }$. Using step 3.1 and the bound on $\sum x_i^{1\mathrm{/}2}$ from step 4.1, we obtain $1=\frac{s}{\mathrm{\mid }X\mathrm{\mid }}+{\sum }_{i=1}^s{x}_i+{\sum }_{i=1}^s\frac{\mathrm{\mid }{D}_i\mathrm{\mid }}{\mathrm{\mid }X\mathrm{\mid }}\le \frac{s}{\mathrm{\mid }X\mathrm{\mid }}+ϵ(ϵ\delta {)}^{-\tau }+\frac{19}{20}{ϵ}^{-1\mathrm{/}2}{\sum }_{i=1}^s{x}_i^{1\mathrm{/}2}\le \frac{s}{\mathrm{\mid }X\mathrm{\mid }}+(ϵ+\frac{19}{20})(ϵ\delta {)}^{-\tau }$. Combining this with steps 1.1 and 3.3 gives $1<\frac{2^{1-1\mathrm{/}\tau }}{\delta }+(ϵ+\frac{19}{20})(ϵ\delta {)}^{-\tau }<1$, a contradiction. Therefore the comb outcome in step 3.1 must occur, and that outcome yields exactly the rooted stable-tooth comb asserted in the Statement.