Mathematica Stack Exchange is a question and answer site for users of Mathematica. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am attempting to use the Combinatorica NumberOfSpanningTrees command for all n-cycle graphs from 3 to 30. I am trying to get a table form showing whether it is true or false that n-cycle graphs have n spanning trees. However Mathematica does not seem to recognize the command. Am I am pre-loading the Combinatorica packages correctly?

<< Combinatorica`
Table[{i, NumberOfSpanningTrees[CycleGraph[i]] == i}, {i, 3, 30}] // TableForm

The output I get is:

enter image description here

I have also tried loading Combinatorica using the Needs["Combinatorica"].

Any ideas?

share|improve this question
up vote 13 down vote accepted

The Combinatorica package is now considered obsolete and not compatible with Mathematica's built-in Graph theory functionality. The function CycleGraph, which you are using, is a built-in function and is not understood by the Combinatorica package. You have to replace CycleGraph[i] simply by Cycle[i], which is the corresponding object in Combinatorica. You can confirm this that by looking at (for example) CycleGraph[5] and ShowGraph[Cycle[5]]:

GraphicsRow[{CycleGraph[5] , ShowGraph[Cycle[5]]}]

Mathematica graphics

Actually, the Combinatorica package still has a lot of functionality that has nothing equivalent in the Kernel (and it is not clear if this will ever change completely). On the other hand it is essentially undocumented (unless you buy the book by Skiena and Pemmaraju) and the quality of Mathematica programming is not great (there are also bugs that never seem to get fixed).

share|improve this answer
Your answer worked perfectly. The difference of the commands between Combinatorica and Mathematica still confuses me. – Nic Young Mar 27 '12 at 3:34
@NicYoung Maybe it's also useful to know that you can convert a new style graph to a Combinatorica graph using the ToCombinatoricaGraph function of the GraphUtilities` package. – Szabolcs Mar 27 '12 at 7:06

Without using the Combinatorica package, you can use

 Table[{i, GraphData[{"Cycle", i}, "SpanningTreeCount"] == i}, 
{i, 3, 20}] // TableForm

to get

 {{3, True}, {4, True}, {5, True}, {6, True}, {7, True}, {8, True}, 
 {9, True}, {10, True}, {11, True}, {12, True}, {13, True}, {14, True}, 
 {15, True}, {16, True}, {17, True}, {18, True}, {19, True}, {20, True}}

This does not work for i>20 since GraphData contains named cycle graphs {"Cycle", i} for i<=20.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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