3
$\begingroup$

This labeled graph is given, I need to find the number of its spanning trees.

enter image description here

The number of spanning trees of the following graph is 3

enter image description here

and the number of spanning trees of this is 8

enter image description here

So as a result the number of spanning trees of the graph is $3^2 \times 8^3 = 4608$ while it is not the correct answer.

$\endgroup$
  • $\begingroup$ you should ask for a refund. $\endgroup$ – Jorge Fernández Hidalgo Mar 14 '15 at 18:14
  • $\begingroup$ where is the question from? could I see a link ? $\endgroup$ – Jorge Fernández Hidalgo Mar 14 '15 at 18:16
  • 1
    $\begingroup$ Well, I agree with you completely. $\endgroup$ – Jorge Fernández Hidalgo Mar 14 '15 at 18:30
  • 1
    $\begingroup$ What difference does it make when the graph is labeled or unlabeled? $\endgroup$ – No one Mar 14 '15 at 18:33
  • 2
    $\begingroup$ The labels look like they take away some of the symmetries you would otherwise have. $\endgroup$ – ililil Mar 14 '15 at 18:34
5
$\begingroup$

Your reasoning looks correct. And, according to Sage, 4608 is indeed the number of spanning trees.

$\endgroup$
  • $\begingroup$ the Sage calculates the labeled graph or unlabeled? $\endgroup$ – No one Mar 14 '15 at 18:46
  • 1
    $\begingroup$ It gives you labelled. If you want unlabelled the answer will be less.If you want unlabelled the answer is less than 1000. So the results is still wrong. $\endgroup$ – Jorge Fernández Hidalgo Mar 14 '15 at 18:47
  • $\begingroup$ Thanks, sounds they made a mistake and it took 8 minutes of my time $\endgroup$ – No one Mar 14 '15 at 18:51

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.