NumberOfSpanningTrees command not working correctly

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:

Any ideas?

-

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]]}]

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).

-
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.

-