Alphabeta Math
LemmaStatement: Literature-sourcedProof: AI-generatedverified 2026-09-24 (gpt-6-sol)
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 H be an ordinary finite graph with h=∣V(H)∣≥3 and leaf v, and put H′=H−v. Let a≥2 and 0<x≤y≤(2h)−1. If the maximum degree of a finite graph G on n≥1 vertices is at most yn, then at least one of the following holds:

  1. ind⁡H(G)>x2a+hnh;
  2. some S⊆V(G) has ∣S∣≥yn and ind⁡H′(G[S])≤ya−2∣S∣h−1;
  3. there are disjoint A,B⊆V(G) with ∣A∣≥yan, ∣B∣≥(1−hy)n, and B is x-sparse to A.

Facts & Assumptions

Given: The graph, leaf and parameters in the statement. Induced-copy counts count labelled induced embeddings.

[F1]

An induced embedding of H′ is an induced embedding of J:=H−{u,v}, where u is the unique neighbor of v, plus one image for u. Once the image of J and a candidate image for u are fixed, a vertex outside their image extends the embedding to H exactly when it is adjacent to the image of u and nonadjacent to the image of J. This uses only the adjacency of the leaf, so no ordering of either graph is needed.

Proof

technique · counting and contradiction
1.1

Suppose outcomes 2 and 3 fail. If yn≤1, choose a singleton S; because ∣H′∣≥2, it has no copy of H′, giving outcome 2. If yan≤1≤yn, take any vertex as A and all its nonneighbors outside A as B. Then ∣A∣≥yan and ∣B∣≥n−1−yn≥(1−hy)n, since (h−1)yn≥1; moreover B is x-sparse to A. Thus failure of both outcomes implies yan>1 and yn>1. In particular y2n≥yan>1, so yn>2.

givenF1
1.2

Choose any set S of ⌈yn⌉ vertices. For each induced embedding ϕ:J↪G[S], let Iϕ be the embeddings of H′ into G[S] restricting to ϕ; the image of u distinguishes their members. Let T be the ϕ for which ∣Iϕ∣≥yan. Failure of outcome 2 gives ind⁡H′(G[S])>ya−2∣S∣h−1. There are at most ∣S∣h−2 maps J→S, while each ϕ∉T has fewer than yan≤ya−1∣S∣ extensions. As y≤1/2, the embeddings over T therefore number more than (ya−2−ya−1)∣S∣h−1≥ya−1∣S∣h−1. Each ϕ has at most ∣S∣ extensions, so |T|>y^{a-1}|S|^{h-2}.\tag{1}

givenalgebra
2.1

Fix ϕ∈T and let P=ϕ(V(J)). Let A′ be the images of u in Iϕ, so ∣A′∣≥yan, and choose A⊆A′ of size ⌈yan⌉. Let B consist of vertices outside S with no neighbor in P. At most (h−2)yn vertices are excluded by adjacency to P, 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 (1−hy)n vertices of B have at most x∣A∣ neighbors in A; otherwise those vertices, with A, would give that outcome. By (2), more than yn−1≥y2n vertices of B have more than x∣A∣ neighbors in A. The last inequality follows from y2n>1 and y≤1/2. Hence there are more than xy^2n|A|\ge xy^{a+2}n^2\ge x^{a+3}n^2\tag{3} edges from B to A.

step 1.1F1algebra
3.1

Every edge in (3), together with ϕ, yields a distinct induced embedding of H: its endpoint in A supplies u, its endpoint in B supplies v, and the latter has no neighbor in P. Different ϕ give different embeddings because restriction to J recovers ϕ. Using (1), (3), ∣S∣≥yn, and x≤y, we get ind⁡H(G)>ya−1∣S∣h−2xa+3n2≥xa+3ya+h−3nh≥x2a+hnh. This is outcome 1.

step 1.2step 2.1F1algebra∎

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