LemmaStatement: Literature-sourcedProof: Literature-sourcedprecheck passaudited 2026-08-31

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Anticonnected block contraction turns an upside-down comb into a pure blockade

Statement

Let $G$ be a $\overline{P_{5}}$ -free graph, let $k \geq 4$ be an integer, and let $B \subseteq V (G)$ . Suppose

((a_{i}, B_{i}) : i \in [k])

is a $(k, ∣ B ∣ / k^{8})$ -comb in $G$ with $B_{i} \subseteq B$ and $a_{i} \notin B$ for every $i \in [k]$ . Suppose also that there is a vertex

v \in V (G) ∖ (B \cup {a_{1}, \dots, a_{k}})

that is complete to $B$ and anticomplete to ${a_{1}, \dots, a_{k}}$ . Then $G [B]$ contains a pure $(k, ∣ B ∣ / k^{10})$ -blockade.

Facts & Assumptions

Given: The graph $G$ , the integer $k$ , the set $B$ , the displayed comb, and the vertex $v$ satisfying the hypotheses above.

[F1]

In the displayed comb, $a_{i}$ is complete to $B_{i}$ and anticomplete to $B_{j}$ for $i \neq j$ , while the blocks are pairwise disjoint and satisfy $∣ B_{i} ∣ \geq ∣ B ∣ / k^{8}$ (Combs in a graph).

[F2]

A set $D$ is an anticonnected component of $G [X]$ precisely when it is the vertex set of a connected component of $\overline{G [X]}$ (Anticonnected graphs and anticonnected components).

[L1]

Distinct anticonnected components of a graph are complete to one another (Distinct connected components are anticomplete, and distinct anticonnected components are complete).

[F3]

A blockade is pure when every pair of distinct blocks is either complete or anticomplete (Complete, anticomplete, pure, weakly sparse, and $x$ -sparse blockades).

[F4]

The graph $P_{5}$ has five vertices and four consecutive edges (Empty and complete graphs, complete bipartite graphs, and the convention that $P_{n}$ and $C_{n}$ have $n$ vertices).

[F5]

Complementation exchanges edges and nonedges (Graph isomorphisms, automorphisms and graph complements).

Proof

technique · contract each comb block to a large anticomponent

1.1

Fix $i \in [k]$ and put $n_{i} : = ∣ B_{i} ∣$ . Suppose first that every anticonnected component of $G [B_{i}]$ has size less than $n_{i} / k$ . Partition the anticonnected components into a minimum number of unions $S_{0}, \dots, S_{r}$ , each of size less than $n_{i} / k$ , and order them by nondecreasing size. Since the parts cover $B_{i}$ , one has $r + 1 > k$ . Minimality gives $∣ S_{j - 1} ∣ + ∣ S_{j} ∣ \geq n_{i} / k$ for $j \geq 1$ , and hence $∣ S_{j} ∣ \geq n_{i} / (2 k) \geq n_{i} / k^{2}$ because $k \geq 4$ . By [L1], the sets $S_{1}, \dots, S_{k}$ are pairwise complete. They therefore form a complete, hence pure, $(k, n_{i} / k^{2})$ -blockade in $G [B]$ . By [F1], $n_{i} / k^{2} \geq ∣ B ∣ / k^{10}$ , which proves the result in this case.

F1L1F3givenchoosealgebra

2.1

We may consequently assume that, for every $i \in [k]$ , the graph $G [B_{i}]$ has an anticonnected component $D_{i}$ with $∣ D_{i} ∣ \geq ∣ B_{i} ∣ / k$ . Choose one such $D_{i}$ . Then $∣ D_{i} ∣ \geq ∣ B_{i} ∣ / k \geq ∣ B ∣ / k^{9} \geq ∣ B ∣ / k^{10}$ , giving the required width bound for every chosen component.

F1F2step 1.1choosealgebra

3.1

Let $i \neq j$ , and suppose that some $u \in D_{j}$ is mixed on $D_{i}$ . The sets of neighbours and nonneighbours of $u$ in $D_{i}$ are both nonempty. Since $\overline{G [D_{i}]}$ is connected, some edge of that complement crosses these two sets. Thus there are $w, z \in D_{i}$ such that $u w \in E (G)$ , $u z \notin E (G)$ , and $w z \notin E (G)$ .

F2step 2.1given

4.1

Among the five vertices $v, a_{i}, u, z, w$ , the nonedges are exactly $v a_{i}, a_{i} u, u z, z w$ . Indeed, the hypotheses on $v$ determine its four incidences; [F1] determines the incidences from $a_{i}$ to $D_{i} \subseteq B_{i}$ and to $u \in D_{j} \subseteq B_{j}$ ; and step 3.1 determines the three remaining incidences. Hence those four nonedges form the path $v - a_{i} - u - z - w$ , so these vertices induce $\overline{P_{5}}$ by [F4] and [F5], contrary to the hypothesis on $G$ . Therefore no vertex of $D_{j}$ is mixed on $D_{i}$ .

F1F4F5step 3.1given

5.1

Applying step 4.1 with both orders of $i, j$ shows that no vertex of either set is mixed on the other. If the pair $(D_{i}, D_{j})$ had both an edge and a nonedge, then the vertices of $D_{j}$ would include one complete to $D_{i}$ and one anticomplete to $D_{i}$ ; every endpoint in $D_{i}$ of the cross-edge would then be mixed on $D_{j}$ , a contradiction. Thus $(D_{i}, D_{j})$ is pure.

step 4.1cases

6.1

The sets $D_{1}, \dots, D_{k}$ are pairwise disjoint subsets of $B$ , have size at least $∣ B ∣ / k^{10}$ by step 2.1, and every cross-pair is pure by step 5.1. Hence they form the required pure $(k, ∣ B ∣ / k^{10})$ -blockade in $G [B]$ .

F1F3step 2.1step 5.1∎

Depends on

Used by

A sparse P₅-free graph either sparsifies further or yields a pure blockade or a large sparse pair Lemma

Dependency tree · two levels

19 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Tung Nguyen, Alex Scott, and Paul Seymour, Induced subgraph density. VII. The five-vertex path, Claim 5.2.2 (standard reference, not scraped)