Ask
Login
0
1.5kviews
Find all spanning trees for the graph G pictured below.
written 4.2 years ago by gravatar for thambisrilalith126 thambisrilalith126 • 20 •   modified 4.2 years ago

Find all spanning trees for the graph G pictured below.

enter image description here
discrete structures and graph theory
ADD COMMENT EDIT
1 Answer
1
59views
written 4.2 years ago by gravatar for thambisrilalith126 thambisrilalith126 • 20

Solution:

Graph G has one circuit v2v1v4v2, and the removal of any edge of the circuit gives a tree. Thus, as shown below, there are three spanning trees for G.

(1) enter image description here

(2) enter image description here

(3) enter image description here
ADD COMMENT EDIT
Please log in to add an answer.