Alphabeta Math
LemmaStatement: AI-adaptedProof: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 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 sparse graph has a prescribed-size induced subgraph of bounded maximum degree

Statement

Let G be a finite graph with at most

ϵV(G)(V(G)1)/2

edges, where ϵ0. If m is an integer with 1m(V(G)+1)/2, then there exists XV(G) with X=m such that the induced subgraph G[X] has maximum degree at most 4ϵ(m1).

Facts & Assumptions

Given: A finite graph G, a real ϵ0, and an integer m with 1m(V(G)+1)/2, such that G has at most ϵV(G)(V(G)1)/2 edges.

Proof

technique · direct
1.1

If m=1, then any single vertex set X works, because a one-vertex graph has maximum degree 0=4ϵ(m1).

given
1.2

If ϵ=0, then G has no edges, so any m-vertex set X has maximum degree 0=4ϵ(m1). Hence we may assume from now on that m2 and ϵ>0. Average the edge count over all (2m1)-vertex subsets YV(G). Some such Y satisfies e(G[Y])ϵ(2m1)(m1), because the expected edge count in a random (2m1)-subset is exactly the global edge count multiplied by the probability that both endpoints of a given edge are chosen.

givenalgebracases
2.1

In this chosen set Y, fewer than m vertices have degree greater than 4ϵ(m1). Otherwise at least m vertices would contribute more than 4ϵ(m1) each to the degree sum, giving 2e(G[Y])>4ϵm(m1)>2ϵ(2m1)(m1), contrary to step 1.2.

step 1.2algebra
3.1

Delete all vertices of Y whose degree in G[Y] exceeds 4ϵ(m1). By step 2.1 at least m vertices remain; choose any m of them and call the resulting set X. Every vertex of G[X] has degree at most its degree in G[Y], so Δ(G[X])4ϵ(m1).

step 2.1choose
4.1

This X has the required size and degree bound.

step 1.1step 1.2step 3.1cases-exhaustive

Used by

Dependency tree · 0 levels

Nothing. This result depends on no other item in the library.

Sources