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 sparse host has many leaf extensions, few smaller copies, or a sparse pair
Statement
Let be an ordinary finite graph with and leaf , and put . Let and . If the maximum degree of a finite graph on vertices is at most , then at least one of the following holds:
- ;
- some has and ;
- there are disjoint with , , and is -sparse to .
Facts & Assumptions
Given: The graph, leaf and parameters in the statement. Induced-copy counts count labelled induced embeddings.
An induced embedding of is an induced embedding of , where is the unique neighbor of , plus one image for . Once the image of and a candidate image for are fixed, a vertex outside their image extends the embedding to exactly when it is adjacent to the image of and nonadjacent to the image of . This uses only the adjacency of the leaf, so no ordering of either graph is needed.
Proof
Suppose outcomes 2 and 3 fail. If , choose a singleton ; because , it has no copy of , giving outcome 2. If , take any vertex as and all its nonneighbors outside as . Then and , since ; moreover is -sparse to . Thus failure of both outcomes implies and . In particular , so .
Choose any set of vertices. For each induced embedding , let be the embeddings of into restricting to ; the image of distinguishes their members. Let be the for which . Failure of outcome 2 gives There are at most maps , while each has fewer than extensions. As , the embeddings over therefore number more than . Each has at most extensions, so |T|>y^{a-1}|S|^{h-2}.\tag{1}
Fix and let . Let be the images of in , so , and choose of size . Let consist of vertices outside with no neighbor in . At most vertices are excluded by adjacency to , whence |B|\ge n-\lceil yn\rceil-(h-2)yn \ge(1-(h-1)y)n-1.\tag{2} Because outcome 3 fails, fewer than vertices of have at most neighbors in ; otherwise those vertices, with , would give that outcome. By (2), more than vertices of have more than neighbors in . The last inequality follows from and . Hence there are more than xy^2n|A|\ge xy^{a+2}n^2\ge x^{a+3}n^2\tag{3} edges from to .
Every edge in (3), together with , yields a distinct induced embedding of : its endpoint in supplies , its endpoint in supplies , and the latter has no neighbor in . Different give different embeddings because restriction to recovers . Using (1), (3), , and , we get This is outcome 1.
Depends on
Used by
Dependency tree · two levels
14 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
- Nguyen, Scott and Seymour, Induced subgraph density IV, Lemma 5.1 (standard reference, not scraped)