申論題

There are 7 problems in this test. No calculators are allowed. Write down detailed steps for
the solution to each problem. Otherwise, no credits for that problem will be given.
4. A bipartite graph is a graph whose vertices can be partitioned into two subsets X and Y so that each edge has one end in X and the other end in Y: A cycle of G is a sequence of vertices u₀, u₁, ..., such that each vertex is distinct, except ,and ； are adjacent for each i = 1,2,. ,I. The length of the cycle is l. A k-cube is a graph whose vertices are binary strings of length k, for some integer k ＞ 0.Two vertices are adjacent if and only if they differ in exactly one bit.