Problems B-3

Solution wanted!

Problems B-2

a. Any one has at most n-1 friends, but there are n people. Hence there are two people with the same number friends.

b. Suppose that a person x who has three friends. If two of them know each other, then they with x are mutual friends. Otherwise on one of them are not friends, it becomes mutual strangers. (Ransey Number)

c. Maximum cut in graph. For any two person x and y, if they are friend then add edge (x,y).
For any graph, we partition the vertices into two group arbitrary. If some vertex x’s neighbors in the same group larger than the neighbors in the opposite group. Then change x’s group. Since change one vertex’s group, we can increase the maximal cut by one. But the maximum cut is finite, so this process will terminate.

d. Proof by undiction.
Base case: If there are three persons, then this case is trivial.
Induction step: Assume that group fewer than k persons can seat around a table. Suppose that we have a table with k-1 persons seated around it. The k-th person has (k/2) friends, so there are two friends who seated nearby. Then the k-th person can seat between they.

Problems B-1

a. For any node in odd level we can color it as one color. For nodes in even level, we color they as another color.

b. 1 -> 2 Color one part as one color. Since there is no edge in the same par, it is 2-colorable.
2 -> 3 If G is 2-colorable, then there is no cycle of odd length. Otherwise there are two adjacent vertex with the same color.
3 -> 1 Select a vertex u into set A. Choose all nodes such the distance with u is even into A. Others are in B. Since there is no odd cycle, A and B must be bipartite.

c. Because for any node, we can color it as the color which is not used in its neighbors.

d. Use the greedy coloring. Color a node as the color which is not used in its neighbors. If we want to use a new color k, there must be k-1 edge adjacent to that node. Let n be the colors used in graph, then |E| < . Since E = O(|V|),  n = .