Given an integer k ≥ 2, let G(k) be the subgraph of the cube Q2k inducedby the vertices in which the number of ones is either k − 1 or k. Computethe number of vertices, the number of edges, and the girth (the length ofa shortest cycle) of G(k). What are the degrees of the vertices in G(k) ?

The number of vertices in G(k) can be computed as follows:

The vertices of Q2k are all 2k-bit binary strings. The vertices of G(k) are those 2k-bit strings with either k-1 or k ones. There are (2k choose k-1) + (2k choose k) such strings.

The number of edges in G(k) can be computed as follows:

An edge in G(k) corresponds to a pair of vertices that differ in exactly one bit. If a vertex has k-1 ones, it is adjacent to k vertices with k ones (by adding a one) and (2k-k+1) vertices with k-1 ones (by flipping a one to a zero). If a vertex has k ones, it is adjacent to k vertices with k-1 ones (by removing a one) and (2k-k) vertices with k ones (by flipping a zero to a one). Therefore, each vertex is of degree 2k.

The girth of G(k) is the length of the shortest cycle. A cycle in G(k) corresponds to a sequence of vertices where each pair of consecutive vertices is adjacent and the first and last vertices are also adjacent. The shortest such cycle has length 4.

The degrees of the vertices in G(k) are all equal to 2k, as explained above.