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 tau-critical graph has no wide pure blockade with cograph pattern
Statement
Let , and let be a -critical graph. Then for every integer , there is no pure blockade in with cograph pattern, of length and width at least , such that each block is a proper subset of .
Facts & Assumptions
Given: A real , a -critical graph , and an integer .
A -critical graph satisfies , while every proper induced subgraph satisfies (A tau-critical graph).
A pure blockade with cograph pattern has additive on its support (A pure blockade with a cograph pattern has additive kappa).
If , then every clique or stable set in is also one in , so (Subgraphs, induced subgraphs and spanning subgraphs, The parameter kappa(G)=alpha(G)omega(G), Cliques, stable sets, the clique number and stability number ).
For positive reals, and (The exponent, product, quotient, and iterated-power laws for positive real bases and real exponents).
Because , the function is increasing on : its derivative is , the factor is positive for because real powers are defined through and is positive, and the derivative-sign theorem then gives monotonicity (Continuity and derivatives of positive-base real powers, Real powers for positive bases, with the zero-base positive-exponent convention, The exponential is positive and satisfies , On an interval , for continuous on and differentiable at every interior point: throughout gives nondecreasing, gives increasing, and give the two decreasing forms; conversely a nondecreasing has and a nonincreasing has wherever it is differentiable, and no strict converse is claimed).
If a blockade has width , then each of its blocks has cardinality at least (Blockades, their length, their width, and their support).
Proof
Suppose for contradiction that is a pure blockade in with cograph pattern, length , width at least , and each a proper subset of . By [L1], each proper induced subgraph satisfies . Since each block has size at least the width, [F1] gives , so [L5] and [L4] yield for every .
Let . Applying [L2] to the blockade and then using step 1.1 yields Then [L3] gives , contradicting the first clause of [L1].
This contradiction proves that no such blockade exists.
Depends on
- A tau-critical graph
- A pure blockade with a cograph pattern has additive kappa
- The pattern graph of a pure blockade
- Cographs by the singleton, disjoint-union, and complete-connection recursion
- The parameter kappa(G)=alpha(G)omega(G)
- Complete, anticomplete, pure, weakly sparse, and $x$-sparse blockades
- Blockades, their length, their width, and their support
- Subgraphs, induced subgraphs and spanning subgraphs
- Cliques, stable sets, the clique number $\omega(G)$ and stability number $\alpha(G)$
- Real powers for positive bases, with the zero-base positive-exponent convention
- The exponent, product, quotient, and iterated-power laws for positive real bases and real exponents
- Continuity and derivatives of positive-base real powers
- On an interval $I$, for $f$ continuous on $I$ and differentiable at every interior point: $f' \ge 0$ throughout gives $f$ nondecreasing, $f' > 0$ gives $f$ increasing, $f' \le 0$ and $f' < 0$ give the two decreasing forms; conversely a nondecreasing $f$ has $f' \ge 0$ and a nonincreasing $f$ has $f' \le 0$ wherever it is differentiable, and no strict converse is claimed
- The exponential is positive and satisfies $\exp(-x)=1/\exp(x)$
Used by
Nothing in the library uses this result yet.
Dependency tree · two levels
51 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
- Maria Chudnovsky, Alex Scott, Paul Seymour, and Sophie Spirkl, Erdos-Hajnal for graphs with no 5-hole, Theorem 5.2 (standard reference, not scraped)