Large Induced Subgraph With Restrict Degrees

Determining the largest size of induced subgraph with restrict degrees is an inter?esting problem in graph theory.Berman et al.[DM,1997]achieved a lot on trees,and further asked a problem to determine for a tree T the size of the largest S(?)V(T)such that all vertices in T[S]have either degree 1 or degree 0(mod k).In this paper,we prove that,for integer k ? 2,every tree T contains an induced subgraph of order at least Ck|V(T)|with all degrees either equal to 1 or 0(mod k),where ck = 3/4when k?2,and ck = 2/3 when ?3,moreover,the bounds are best possible.This solves the problem of Berman et al.