MATH 4610H 2011 Assignment 3 Due April 8 2011 1. Find the clique number and the

MATH 4610H 2011 Assignment 3 Due April 8 2011 1. Find the clique number and the chromatic number of the graph G in Figure 1. Justify your answers. Do you notice anything unusual about this graph? Figure 1 2. 1.6.2 #1. Recall that avg deg (G) denotes the average degree of vertices in G. Prove or give a coun- terexample to the following statement:(G) 1 + avg deg (G) : 3. 1.6.2 #8. Let G be a graph of order n. Prove that (a) n (G) ??G; [Hint: Use the inequality of Exercise 1.6.2 #6 and notice that (G) = ! ??G.
MATH 4610H 2011 Assignment 3 Due April 8 2011 1. Find the clique number and the chromatic number of the graph G in Figure 1. Justify your answers. Do you notice anything unusual about this graph? Figure 1 2. 1.6.2 #1. Recall that avg deg (G) denotes the average degree of vertices in G. Prove or give a coun- terexample to the following statement:(G) 1 + avg deg (G) : 3. 1.6.2 #8. Let G be a graph of order n. Prove that (a) n (G) ??G; [Hint: Use the inequality of Exercise 1.6.2 #6 and notice that (G) = ! ??G.] (b) 2pn (G) + ??G: [Hint: First show that (G) + n (G) 2pn then apply the result of part (a).] 4. 1.7.2 #3. Let G be a bipartite graph. Show that G has a matching of size at least jE (G)j =(G). [We assume here that (G) 6= 0. Hint: Use induction on the number of vertices in G.] 5. (a) Consider the 4 8 Latin rectangle R = 1 2 3 4 5 6 7 8 4 3 2 5 7 1 8 6 7 8 1 6 2 3 4 5 6 1 5 3 8 4 2 7 : Construct a bipartite graph and then nd a perfect matching in that graph to extend R to a 58 Latin rectangle. (b) Solve the assignment problem with the following cost table: Task 1 2 3 4 A 4 1 0 1 Assignee B 1 3 4 0 C 3 2 1 3 D 2 2 3 0 1
Attachments: