Find all possible spanning trees for the graph SolutionEdge

Find all possible spanning trees for the graph

Solution

Edge bc has to be present in all such spanning trees as vertex c is incident only on this edge

Case 1: ab is included in spanning tree

          Case 1.1 bd is present. Then the tree is consisting of these three edges

            {bc,bd,ba}

         Case 1.2 ad is present. Then the tree is consisting of these three edges

            {bc,ba,ad}

Case 2: ab is not present

Then spanning tree is: {bc,bd,ad}