Question

The spanning tree will be maximally acyclic if ____________

(a) one additional edge makes a cycle in the tree

(b) two additional edges makes a cycle in the tree

(c) removing one edge makes the tree cycle free

(d) removing two edges make the tree cycle free

I have been asked this question in final exam.

My question is based upon Spanning Trees topic in chapter Trees of Discrete Mathematics

Answer 1

Right choice is (a) one additional edge makes a cycle in the tree

For explanation I would say: A connected graph G can have more than one spanning tree. Removing one edge from the spanning tree will make the graph disconnected and the spanning tree is minimally connected. Adding one edge to the spanning tree will create a circuit or loop and the spanning tree is maximally acyclic.