Probability Level 4

A kk-regular graph satisfies the neighborhood diversity condition if it is possible to label each vertex with one of 1,2,3,,k1, 2, 3, \ldots, k such that for each vertex, all its neighbors have different labels.

Determine the sum of all nn satisfying 1n10001 \le n \le 1000 such that the nn-hypercube graph satisfies the neighborhood diversity condition.


  • In a kk-regular graph, each vertex has kk neighbors.
  • An nn-hypercube graph is the graph of an nn-dimensional hypercube. In other words, its vertices are elements of {0,1}n\{0,1\}^n (that is, nn-tuples with each component 0 or 1), and two vertices are adjacent if and only if they differ in exactly one component.
  • The labeling is not necessarily a proper vertex coloring: two adjacent vertices may have the same label.

Problem Loading...

Note Loading...

Set Loading...