Calculator Inputs
Formula Used
The calculator uses the Matrix-Tree theorem. First build the adjacency matrix A. Next compute the degree matrix D. Then form the Laplacian matrix:
L = D − A
Delete any one row and the matching column from L. The determinant of that cofactor gives the spanning tree count:
τ(G) = det(Lᵢ)
For several preset families, closed-form checks are also known: complete graphs use Cayley’s formula, cycles use n, paths use 1, and complete bipartite graphs use m^(n−1) × n^(m−1).
How to Use This Calculator
- Select a graph family or choose the custom edge list mode.
- Enter the total vertex count, or the bipartite partition sizes.
- For custom graphs, add one undirected edge per line.
- Choose which Laplacian row and column to remove.
- Press Count Spanning Trees to see the result above the form.
- Review the matrices, graph plot, degree plot, and summary metrics.
- Use the CSV or PDF buttons to save the output.
Example Data Table
| Graph | Vertices | Edges | Spanning Trees | Check |
|---|---|---|---|---|
| Complete graph K₄ | 4 | 6 | 16 | 4^(4−2) |
| Cycle graph C₅ | 5 | 5 | 5 | n |
| Path graph P₆ | 6 | 5 | 1 | Every tree has one spanning tree. |
| Star graph S₆ | 6 | 5 | 1 | Every tree has one spanning tree. |
| Complete bipartite K₃,₄ | 7 | 12 | 432 | 3^(4−1) × 4^(3−1) |
FAQs
1. What does this calculator count?
It counts the number of distinct spanning trees in an undirected simple graph. A spanning tree connects every vertex using the fewest possible edges and contains no cycle.
2. What happens if the graph is disconnected?
A disconnected graph has no spanning tree covering all vertices. The calculator detects disconnected components and returns zero for the spanning tree count.
3. Why remove a row and column from the Laplacian?
Kirchhoff’s theorem says any cofactor of the Laplacian matrix equals the spanning tree total. Removing one matching row and column produces that cofactor determinant.
4. Are duplicate edges allowed?
The page treats the graph as a simple undirected graph. Duplicate edges, self-loops, and invalid pairs are removed before the count is computed.
5. Can I use preset graph families?
Yes. The calculator supports complete, cycle, path, star, wheel, and complete bipartite graphs. These are useful for both learning and quick verification.
6. Why might large graphs show approximate results?
Very large determinant values can exceed standard integer ranges. When the GMP extension is unavailable, the page falls back to numeric Bareiss elimination for practical computation.
7. What does the cyclomatic number mean?
It measures how many independent cycles exist in the graph. For connected graphs, it equals edges minus vertices plus one.
8. What do the CSV and PDF buttons export?
They export the summary section shown after calculation. CSV saves the key metrics, while PDF captures the visible result block for reporting or documentation.