1
$\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$
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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.