Abstract We study minimum degree conditions that guarantee that an ‐vertex graph is rigid in . For small values of , we obtain a tight bound: For , every ‐vertex graph with minimum degree at least is rigid in . For larger values of , we achieve an approximate result: For , every ‐vertex graph with minimum degree at least is rigid in . This bound is tight up to a factor of two in the coefficient of . As a byproduct of our proof, we also obtain the following result, which may be of independent interest: For , every ‐vertex graph with minimum degree at least has pseudoachromatic number at least ; namely, the vertex set of such a graph can be partitioned into subsets such that there is at least one edge between each pair of subsets. This is tight.
Krivelevich et al. (Thu,) studied this question.