2
$\begingroup$

The solution to the number of spanning trees of the graph below is given by $3 \times 2 \times 3 = 18$. I'm not sure how to get this. Please assist. Thanks!

enter image description here

Notes: Just in case anyone was wondering, I drew the graph using the tool on http://illuminations.nctm.org/Activity.aspx?id=3550 and got the image by using the snipping tool on Windows.

$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

Any spanning tree in the graph must contain exactly one CD edge, and this edge can be chosen in two ways. For the subgraph to be connected, C must be in the same component as A and B. Thus two of the three edges in the triangle ABC need to be included, and these two edges can be chosen in 3 ways. Similarly the two edges in the triangle CEF can be chosen in 3 ways. Thus the number of spanning trees is $2 \times 3 \times 3 =18$.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .