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 1≤m≤(∣V(G)∣+1)/2, then there exists X⊆V(G) with ∣X∣=m such that the induced subgraph G[X] has maximum degree at most 4ϵ(m−1).

Facts & Assumptions

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

Proof

technique · direct
1.1given

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

1.2givenalgebracases

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

2.1step 1.2algebra

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

3.1step 2.1choose

Delete all vertices of Y whose degree in G[Y] exceeds 4ϵ(m−1). 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ϵ(m−1).

4.1step 1.1step 1.2step 3.1cases-exhaustive∎

This X has the required size and degree bound.

Used by

Dependency tree · 0 levels

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

Sources