問題詳情

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 u0, u1, ...,

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.


【題組】(a) Show that every h-cube is bipartite by partitioning its vertexes into X and Y, andthen show that every edge connects some vertex in X and another vertex in Y.

參考答案