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 = .

Exercises B.5-7

Proof by contradiction.
Suppose that a tree T with L leaves contains no subtree having between L/3 and 2L/3 nodes. Let root be . We find = children of with more leaves. Since the tree has only L leaf nodes, so there must be one i such that has more than 2L/3 leaves nodes and has fewer than L/3 leaves. Since sibling of has fewer than L/3 leaves, can’t have 2L/3 leaves.

Exercises B.5-6

Proof by induction.
Base case: If tree T has just one node. Trivial.
Induction step: Assume that for all tree size smaller than k. Suppose that a tree T with size k. If T’s root has a subtree, then is at most 0.5. Because the depth increase by one. Since T has at most two subtrees, the inequality is hold.

Exercises B.5-5

Proof by induction.
Base case: A tree with one node. Trivial.
Induction step: Assuem E = I+2n for all tree with size smaller k. Suppose that a tree T with size k. We can construct T’ by removing a internal leaf node x, then E’ = I’ + 2n-2. When adding x back, we must add two external node. So E = I + 2n – 2 + 2 = I + 2n.

Exercises B.5-4

Base case: If a tree has only one node, then the height = 1 > .
Induction step: Assume binary tree with n nodes has height at least , for all n < k. Suppose that a binary tree T with k nodes. We can construct a tree T’ by remove a node from T, such that the height of T’ > . Because except k is power of 2. T’s height = T’s height > . If k is power of 2, then the inequality is also hold.

Exercises B.5-3

Base case: A tree with three vertices, one is root and others are leaves. The number of degree-2 nodes is 1 less than the number of leaves.
Induction step: Assume the number of degree-2 nodes is 1 less than the number of leaves for all tree with size smaller than k-1. Suppose that a tree with k nodes, we can find a leaf x and remove it. If x’s parent’s degree is 1, then both the number of degree-2 nodes and the number of leaves don’t change. If x’s parents degree is 2, then both the number of degree-2 nodes and the number of leaves decrease by one. The proposition that number of degree-2 nodes is 1 less than the number of leaves is hold.

Exercises B.5-2

Because G is acyclic, there is no directed cycle. But if there one vertex which has two path to another vertex, then the undirected version also has cycle. However has a unique path to all the other vertices. Hence the undirected version must be connected and has no cycle, which is a tree.

Exercises B.5-1