LemmaStatement: Literature-sourcedProof: AI-generatedprecheck 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.

A dense bipartite side has a small hitting set

Statement

Let $A, B$ be disjoint nonempty vertex sets in a graph, and let $x \in (0, 1]$ . Assume every vertex of $B$ has at least $x ∣ A ∣$ neighbours in $A$ . Then there is a set $S \subseteq A$ with $∣ S ∣ \leq ⌈ 1 / x ⌉$ that meets the neighbourhood in $A$ of at least half of the vertices of $B$ .

Facts & Assumptions

Given: Disjoint nonempty vertex sets $A, B$ in a graph and a real $x \in (0, 1]$ such that every $b \in B$ has at least $x ∣ A ∣$ neighbours in $A$ .

[L1]

If $S = A$ , then every neighbourhood in $A$ is hit; otherwise a uniform $m$ -subset of $A$ misses a fixed $b$ -neighbourhood with probability at most $(1 - x)^{m}$ .

Proof

technique · probabilistic existence

1.1L1givenchoosealgebra

If $⌈ 1 / x ⌉ \geq ∣ A ∣$ , take $S : = A$ and every neighbourhood in $A$ is hit. Otherwise let $m : = ⌈ 1 / x ⌉ < ∣ A ∣$ and choose a subset $S \subseteq A$ uniformly among all subsets of size $m$ . For a fixed vertex $b \in B$ , the probability that $S \cap N (b) = \emptyset$ is at most $(1 - x)^{m} \leq e^{- x m} \leq e^{- 1} < 1 / 2$ .

2.1step 1.1algebra∎

In the first case every vertex of $B$ is hit. In the second case the expected number of vertices of $B$ whose neighbourhood misses $S$ is less than $∣ B ∣ / 2$ , so some choice of $S$ misses fewer than half of $B$ . Thus in either case there is a set $S \subseteq A$ with $∣ S ∣ \leq ⌈ 1 / x ⌉$ that meets the neighbourhood of at least half of the vertices of $B$ .

Depends on

Adjacency, incidence, open and closed neighbourhoods, vertex degree, minimum degree and maximum degree

Used by

Dependency tree · two levels

3 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, Lemma 4.2 (standard reference, not scraped)