The Setting
Let be a finite simple graph, and write . The degree of a vertex is its number of neighbours in . For , the average degree of is the real number given in (1): (1) For a positive real number , the degree cutoff is the subset of defined in (2): (2)
For a subset , the induced subgraph has vertex set and the edges of with both endpoints in . The independence number is the largest cardinality of a subset of containing no adjacent pair.
The Claim
Theorem 1. Let be a finite simple graph with . If and , then the degree cutoff in (2) satisfies (3)✦ For every subset , (4)✦
In the paper, with denoting the complete graph on vertices, the result reads: for a -free graph with vertices and average degree , retaining vertices of original degree at most gives an induced -free graph on at least vertices with maximum degree at most , and Proposition 6.1 yields , where is the constant in that proposition, so one may take .
What Is Checked
The bound (3) is stated for finite simple graphs and a positive real satisfying the degree sum identity, and (4) is stated for every vertex subset of a finite simple graph.