Please answer d.1 and d.2 2. (20pts) Answer each question by choosing the correc
ID: 3909927 • Letter: P
Question
Please answer d.1 and d.2
2. (20pts) Answer each question by choosing the correct item. (a) Consider the graph G1-(V,E) with V and E given as follows V-(a, b, c, d, e,f How many simple cycle(s) does G have? (b) How many connected components does G1 have? c)How many edges does a spanning tree of G1 have? (d) Now consider any connected graph G (V.E). Suppose it includes exactly two simple cycles. How many edges should be eliminated so G becomes a tree? Fill in the two blanks to complete the reasoning. Let C be one of the two cycles. We need to remove at least one edge of C so C no longer exists. Let it be e. Suppose the removal of e eliminates C and the other simple cycle. Then G would have include at least fd.t cycles We therefore need to eliminate another edge. We conclude that exactly(d.2) edges need to be removed so G becomes a tree. e) Suppose G includes exactly three simple cycles. How many edges must be removed so G becomes a tree?Explanation / Answer
G is a graph which have exatly 2 cycles. lets call one of the cycle is C. Inorder to remove cycles from the graph G, we need to remove some edges, so that G becomes cycle free graph(tree). To remove cycle C from we need to remove edge 'e'. But when removing edge "e", it can eliminate both cycle C and other cycle also. So removing edge "e" eliminates both the cycles in the graph. So, if G has one more cycle, then we need to eliminate one more edge.
d.1 is 1
d.2 is 1
Lets frame with d.1 and d.2 now
Let C be one of the tow cycles. we need to remove at least one edge of C.so C no longer exists. let it be e. Suppose the removal of e eliminates C and other simple cycle. Then G would have include at least 1 cycle. we therefore need to eliminate another edge. we conclude that exatly 1 edge need to be removed so G becomes a tree.