Discrete Mathematics

Graph Theory

Consider the graph G given below.

a f e d

b c

(a) Is G bipartite? Justify your answer.

(b) Is G a tree? Justify your answer.

(c) What is the chromatic number of G? Justify your answer.

(d) Which edges could be removed in order to obtain a spanning tree for G? Draw the resulting

spanning tree.

4. [4 + 4 + 5 + 5 = 18 pts] (Graph Theory) Consider the graph G given below. (a Is G bipartite? Justify your answer. (b (c (d 1Which edges could be removed in order to obtain a spanning tree for G? Draw the resulting Is G a tree? Justify your answer. 1What is the chromatic number of G? Justify your answer. ) ) ) ) spanning tree