How Many Spanning Trees Can a Graph Have?

  • Context: Undergrad 
  • Thread starter Thread starter Marvin94
  • Start date Start date
  • Tags Tags
    Graph Trees
Click For Summary
SUMMARY

The discussion centers on calculating the number of spanning trees in a graph based on its nodes and edges. It establishes that without labeling the vertices and edges, determining the number of spanning trees is not feasible. The "deletion-contraction" theorem is highlighted as a definitive method for counting spanning trees, allowing recursive application until simpler graphs are obtained. Additionally, calculating a cofactor of the graph's Laplacian matrix is presented as another viable method, contingent upon labeling the graph.

PREREQUISITES
  • Understanding of graph theory concepts, specifically spanning trees
  • Familiarity with the deletion-contraction theorem
  • Knowledge of Laplacian matrices in graph theory
  • Ability to label vertices and edges in a graph
NEXT STEPS
  • Study the "deletion-contraction" theorem in detail
  • Learn how to compute the Laplacian matrix of a graph
  • Explore recursive algorithms for counting spanning trees
  • Investigate practical applications of spanning trees in network design
USEFUL FOR

Students and professionals in mathematics, computer science, and network engineering who are interested in advanced graph theory and its applications.

Marvin94
Messages
41
Reaction score
0
How many trees are in a graph if the number of nodes and the number of branches (or meshes) is given? I refer to the trees which has to "walk" through the nodes along the given branches (so no tree between 2 nodes without a connecting branch between them)
 
Physics news on Phys.org
I don't think there is a way to count the number of spanning trees of a graph if you only have the number of nodes and branches.

However, If you are able to label the vertices and edges of a graph then there is the "deletion-contraction" theorem which says that the number of spanning trees of a graph, G, is equal to the number of spanning trees of G by deleting an edge plus the number of spanning trees of the G by contracting an edge. From there, it's clear to see that you can recursively apply this theorem until you end up with a bunch of small graphs with trees that you can count easily. Another method is to calculate any cofactor of the graph's laplacian matrix (https://en.wikipedia.org/wiki/Laplacian_matrix), but again to do so you must be able to label the graph.

I hope this helps a bit.
 

Similar threads

Undergrad How do leaf nodes behave in regression decision trees?
  • · Replies 6 ·
Replies
6
Views
3K
Undergrad Find Smallest Subtree of G w/ Nodes from S
  • · Replies 5 ·
Replies
5
Views
2K
Undergrad Number of edges in a tree digraph
  • · Replies 5 ·
Replies
5
Views
2K
Comp Sci Number of trees in a Fibonacci Heap without CASCADING-CUT
  • · Replies 11 ·
Replies
11
Views
2K
Electrical Why Do Some Sections of My Pre-Lit Christmas Tree Not Light Up?
  • · Replies 5 ·
Replies
5
Views
7K
Undergrad How Many Regular Ternary Ordered Trees with Height 3 Exist?
  • · Replies 2 ·
Replies
2
Views
1K
MHB How many new branches will the complement graph of a deleted edge have?
  • · Replies 11 ·
Replies
11
Views
2K
When to Use a Two-Port Representation for a Quadripole in External Circuits?
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad How to Land a Tree Flat in 3/4 Rotation: Solving the Equations
  • · Replies 19 ·
Replies
19
Views
2K
Algorithm for computing the depths of all the nodes of tree
  • · Replies 1 ·
Replies
1
Views
3K