Skip to main content
added 933 characters in body
Source Link
Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104

I started this, went to dinner, and came back to see that David Speyer anticipated me, but I'll put it in anyway. Here is a theorem, a story and a result somewhat along the lines you want.

Theorem: If $\mathcal{F}$ is a forest with $n$ (labelled) vertices and $k$ connected components of sizes $n_1,n_2,\cdots,n_k$ then the number $T(\mathcal{F})$ of completions to a labelled tree is $n_1n_2\cdots n_kn^{k-2}.$

The proof is left to the interested reader but it is left to the interested reader but it is an easy induction on $k \ge 1$ and includes at the other extreme of $k=n$ the usual enumeration of labelled trees. (see below)

Story: I discovered this as an undergraduate. Of course I knew that there are like 100 proofs of the $n^{n-2}$ theorem but I thought the induction on the number of undetermined edges might be a slightly new twist. I had the occasion to show it to Frank Harary who said: "This is well written and deserves a place in the literature, I am editing a new journal, submit it." So I did. A few months later it came back with a letter from Haray: "I got the referees report, never submit this anywhere again!" and I didn't (until now!).

So for your Q2: Label an edge from $v_i$ to $v_j$ as $e_{i,j}$ (with $i \lt j$). Then in the Laplacian matrix if you plug in $n-1+\sum_j e_{i,j}$ instead of $\deg(v_i)$ and $-1-e_{i,j}$ instead of -1 when that edge connects vertices $i$ and $j$, you get a modified combinatorial Laplacian. Taking the determinant of any minor of this matrix gives a modified Kirchhoff polynomial which is a weighted enumeration of the spanning forests of the graph, where each term is a monomial contains the variables for all the edges in a given forest $\mathcal{F}$ and the coefficient is $T(\mathcal{F}).$ So this polynomial spits out all the spanning forests including the empty one (times $n^{n-2}$) ,each of the spanning trees, and everything in between.

Looking over the comments i see that one could just add the identity to the original combinatorial Laplacian (i.e. set all the $\lambda_{ii}=1$) and get a sum over the spanning trees with positive weights.

the proof The case $k=1$ is obvious (alternately, start with $k=2$.) Suppose now that the result is true for forests made of $k-1$ trees and that $\mathcal{F}$ is a forest with $n$ (labelled) vertices and $k$ connected components $T_1,T_2,\cdots,T_k$ of sizes $n_1,n_2,\cdots,n_k$. We will find $(k-1)T(\mathcal{F})$, the number of ways to add a distinguished edge (obtaining a forest with $k-1$ components) and then complete that to a tree. If the distinguished edge goes from $T_i$ to $T_j$ then, by assumption, there are $(n_i+n_j)n_1n_2\cdots\widehat{n_i}\cdots\widehat{n_j}\cdots n_kn^{k-3}$ such completions. Since there are $n_in_j$ such edges, the number mentioned is $$\sum_{1\le i<j \le k}(n_i+n_j)\left(n_1\cdots n_kn^{k-3}\right)=(k-1)\sum_{i=1}^kn_i\left( n_1\cdots n_kn^{k-3}\right)=(k-1)n\left( n_1\cdots n_kn^{k-3}\right)$$ Hence, $T(\mathcal{F})=n_1n_2\cdots n_kn^{k-2}.$

I started this, went to dinner, and came back to see that David Speyer anticipated me, but I'll put it in anyway. Here is a theorem, a story and a result somewhat along the lines you want.

Theorem: If $\mathcal{F}$ is a forest with $n$ (labelled) vertices and $k$ connected components of sizes $n_1,n_2,\cdots,n_k$ then the number $T(\mathcal{F})$ of completions to a labelled tree is $n_1n_2\cdots n_kn^{k-2}.$

The proof is left to the interested reader but it is an easy induction on $k \ge 1$ and includes at the other extreme of $k=n$ the usual enumeration of labelled trees.

Story: I discovered this as an undergraduate. Of course I knew that there are like 100 proofs of the $n^{n-2}$ theorem but I thought the induction on the number of undetermined edges might be a slightly new twist. I had the occasion to show it to Frank Harary who said: "This is well written and deserves a place in the literature, I am editing a new journal, submit it." So I did. A few months later it came back with a letter from Haray: "I got the referees report, never submit this anywhere again!" and I didn't (until now!).

So for your Q2: Label an edge from $v_i$ to $v_j$ as $e_{i,j}$ (with $i \lt j$). Then in the Laplacian matrix if you plug in $n-1+\sum_j e_{i,j}$ instead of $\deg(v_i)$ and $-1-e_{i,j}$ instead of -1 when that edge connects vertices $i$ and $j$, you get a modified combinatorial Laplacian. Taking the determinant of any minor of this matrix gives a modified Kirchhoff polynomial which is a weighted enumeration of the spanning forests of the graph, where each term is a monomial contains the variables for all the edges in a given forest $\mathcal{F}$ and the coefficient is $T(\mathcal{F}).$ So this polynomial spits out all the spanning forests including the empty one (times $n^{n-2}$) ,each of the spanning trees, and everything in between.

Looking over the comments i see that one could just add the identity to the original combinatorial Laplacian (i.e. set all the $\lambda_{ii}=1$) and get a sum over the spanning trees with positive weights.

I started this, went to dinner, and came back to see that David Speyer anticipated me, but I'll put it in anyway. Here is a theorem, a story and a result somewhat along the lines you want.

Theorem: If $\mathcal{F}$ is a forest with $n$ (labelled) vertices and $k$ connected components of sizes $n_1,n_2,\cdots,n_k$ then the number $T(\mathcal{F})$ of completions to a labelled tree is $n_1n_2\cdots n_kn^{k-2}.$

The proof is left to the interested reader but it is an easy induction on $k \ge 1$ and includes at the other extreme of $k=n$ the usual enumeration of labelled trees. (see below)

Story: I discovered this as an undergraduate. Of course I knew that there are like 100 proofs of the $n^{n-2}$ theorem but I thought the induction on the number of undetermined edges might be a slightly new twist. I had the occasion to show it to Frank Harary who said: "This is well written and deserves a place in the literature, I am editing a new journal, submit it." So I did. A few months later it came back with a letter from Haray: "I got the referees report, never submit this anywhere again!" and I didn't (until now!).

So for your Q2: Label an edge from $v_i$ to $v_j$ as $e_{i,j}$ (with $i \lt j$). Then in the Laplacian matrix if you plug in $n-1+\sum_j e_{i,j}$ instead of $\deg(v_i)$ and $-1-e_{i,j}$ instead of -1 when that edge connects vertices $i$ and $j$, you get a modified combinatorial Laplacian. Taking the determinant of any minor of this matrix gives a modified Kirchhoff polynomial which is a weighted enumeration of the spanning forests of the graph, where each term is a monomial contains the variables for all the edges in a given forest $\mathcal{F}$ and the coefficient is $T(\mathcal{F}).$ So this polynomial spits out all the spanning forests including the empty one (times $n^{n-2}$) ,each of the spanning trees, and everything in between.

Looking over the comments i see that one could just add the identity to the original combinatorial Laplacian (i.e. set all the $\lambda_{ii}=1$) and get a sum over the spanning trees with positive weights.

the proof The case $k=1$ is obvious (alternately, start with $k=2$.) Suppose now that the result is true for forests made of $k-1$ trees and that $\mathcal{F}$ is a forest with $n$ (labelled) vertices and $k$ connected components $T_1,T_2,\cdots,T_k$ of sizes $n_1,n_2,\cdots,n_k$. We will find $(k-1)T(\mathcal{F})$, the number of ways to add a distinguished edge (obtaining a forest with $k-1$ components) and then complete that to a tree. If the distinguished edge goes from $T_i$ to $T_j$ then, by assumption, there are $(n_i+n_j)n_1n_2\cdots\widehat{n_i}\cdots\widehat{n_j}\cdots n_kn^{k-3}$ such completions. Since there are $n_in_j$ such edges, the number mentioned is $$\sum_{1\le i<j \le k}(n_i+n_j)\left(n_1\cdots n_kn^{k-3}\right)=(k-1)\sum_{i=1}^kn_i\left( n_1\cdots n_kn^{k-3}\right)=(k-1)n\left( n_1\cdots n_kn^{k-3}\right)$$ Hence, $T(\mathcal{F})=n_1n_2\cdots n_kn^{k-2}.$

added 211 characters in body
Source Link
Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104

I started this, went to dinner, and came back to see that David Speyer anticipated me, but I'll put it in anyway. Here is a theorem, a story and a result somewhat along the lines you want.

Theorem: If $\mathcal{F}$ is a forest with $n$ (labelled) vertices and $k$ connected components of sizes $n_1,n_2,\cdots,n_k$ then the number $T(\mathcal{F})$ of completions to a labelled tree is $n_1n_2\cdots n_kn^{k-2}.$

The proof is left to the interested reader but it is an easy induction on $k \ge 1$ and includes at the other extreme of $k=n$ the usual enumeration of labelled trees.

Story: I discovered this as an undergraduate. Of course I knew that there are like 100 proofs of the $n^{n-2}$ theorem but I thought the induction on the number of undetermined edges might be a slightly new twist. I had the occasion to show it to Frank Harary who said: "This is well written and deserves a place in the literature, I am editing a new journal, submit it." So I did. A few months later it came back with a letter from Haray: "I got the referees report, never submit this anywhere again!" and I didn't (until now!).

So for your Q2: Label an edge from $v_i$ to $v_j$ as $e_{i,j}$ (with $i \lt j$). Then in the Laplacian matrix if you plug in $n+\sum_j e_{i,j}$$n-1+\sum_j e_{i,j}$ instead of $\deg(v_i)$ and $-1-e_{i,j}$ instead of -1 when that edge connects vertices $i$ and $j$, you get a modified combinatorial Laplacian. Taking the determinant of any minor of this matrix gives a modified Kirchhoff polynomial which is a weighted enumeration of the spanning forests of the graph, where each term is a monomial contains the variables for all the edges in a given forest $\mathcal{F}$ and the coefficient is $T(\mathcal{F}).$ So this polynomial spits out all the spanning forests including the empty one (times $n^{n-2}$) ,each of the spanning trees, and everything in between.

Looking over the comments i see that one could just add the identity to the original combinatorial Laplacian (i.e. set all the $\lambda_{ii}=1$) and get a sum over the spanning trees with positive weights.

I started this, went to dinner, and came back to see that David Speyer anticipated me, but I'll put it in anyway. Here is a theorem, a story and a result somewhat along the lines you want.

Theorem: If $\mathcal{F}$ is a forest with $n$ (labelled) vertices and $k$ connected components of sizes $n_1,n_2,\cdots,n_k$ then the number $T(\mathcal{F})$ of completions to a labelled tree is $n_1n_2\cdots n_kn^{k-2}.$

The proof is left to the interested reader but it is an easy induction on $k \ge 1$ and includes at the other extreme of $k=n$ the usual enumeration of labelled trees.

Story: I discovered this as an undergraduate. Of course I knew that there are like 100 proofs of the $n^{n-2}$ theorem but I thought the induction on the number of undetermined edges might be a slightly new twist. I had the occasion to show it to Frank Harary who said: "This is well written and deserves a place in the literature, I am editing a new journal, submit it." So I did. A few months later it came back with a letter from Haray: "I got the referees report, never submit this anywhere again!" and I didn't (until now!).

So for your Q2: Label an edge from $v_i$ to $v_j$ as $e_{i,j}$ (with $i \lt j$). Then in the Laplacian matrix if you plug in $n+\sum_j e_{i,j}$ instead of $\deg(v_i)$ and $-1-e_{i,j}$ instead of -1 when that edge connects vertices $i$ and $j$, you get a modified combinatorial Laplacian. Taking the determinant of any minor of this matrix gives a modified Kirchhoff polynomial which is a weighted enumeration of the spanning forests of the graph, where each term is a monomial contains the variables for all the edges in a given forest $\mathcal{F}$ and the coefficient is $T(\mathcal{F}).$ So this polynomial spits out all the spanning forests including the empty one (times $n^{n-2}$) ,each of the spanning trees, and everything in between.

I started this, went to dinner, and came back to see that David Speyer anticipated me, but I'll put it in anyway. Here is a theorem, a story and a result somewhat along the lines you want.

Theorem: If $\mathcal{F}$ is a forest with $n$ (labelled) vertices and $k$ connected components of sizes $n_1,n_2,\cdots,n_k$ then the number $T(\mathcal{F})$ of completions to a labelled tree is $n_1n_2\cdots n_kn^{k-2}.$

The proof is left to the interested reader but it is an easy induction on $k \ge 1$ and includes at the other extreme of $k=n$ the usual enumeration of labelled trees.

Story: I discovered this as an undergraduate. Of course I knew that there are like 100 proofs of the $n^{n-2}$ theorem but I thought the induction on the number of undetermined edges might be a slightly new twist. I had the occasion to show it to Frank Harary who said: "This is well written and deserves a place in the literature, I am editing a new journal, submit it." So I did. A few months later it came back with a letter from Haray: "I got the referees report, never submit this anywhere again!" and I didn't (until now!).

So for your Q2: Label an edge from $v_i$ to $v_j$ as $e_{i,j}$ (with $i \lt j$). Then in the Laplacian matrix if you plug in $n-1+\sum_j e_{i,j}$ instead of $\deg(v_i)$ and $-1-e_{i,j}$ instead of -1 when that edge connects vertices $i$ and $j$, you get a modified combinatorial Laplacian. Taking the determinant of any minor of this matrix gives a modified Kirchhoff polynomial which is a weighted enumeration of the spanning forests of the graph, where each term is a monomial contains the variables for all the edges in a given forest $\mathcal{F}$ and the coefficient is $T(\mathcal{F}).$ So this polynomial spits out all the spanning forests including the empty one (times $n^{n-2}$) ,each of the spanning trees, and everything in between.

Looking over the comments i see that one could just add the identity to the original combinatorial Laplacian (i.e. set all the $\lambda_{ii}=1$) and get a sum over the spanning trees with positive weights.

Source Link
Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104

I started this, went to dinner, and came back to see that David Speyer anticipated me, but I'll put it in anyway. Here is a theorem, a story and a result somewhat along the lines you want.

Theorem: If $\mathcal{F}$ is a forest with $n$ (labelled) vertices and $k$ connected components of sizes $n_1,n_2,\cdots,n_k$ then the number $T(\mathcal{F})$ of completions to a labelled tree is $n_1n_2\cdots n_kn^{k-2}.$

The proof is left to the interested reader but it is an easy induction on $k \ge 1$ and includes at the other extreme of $k=n$ the usual enumeration of labelled trees.

Story: I discovered this as an undergraduate. Of course I knew that there are like 100 proofs of the $n^{n-2}$ theorem but I thought the induction on the number of undetermined edges might be a slightly new twist. I had the occasion to show it to Frank Harary who said: "This is well written and deserves a place in the literature, I am editing a new journal, submit it." So I did. A few months later it came back with a letter from Haray: "I got the referees report, never submit this anywhere again!" and I didn't (until now!).

So for your Q2: Label an edge from $v_i$ to $v_j$ as $e_{i,j}$ (with $i \lt j$). Then in the Laplacian matrix if you plug in $n+\sum_j e_{i,j}$ instead of $\deg(v_i)$ and $-1-e_{i,j}$ instead of -1 when that edge connects vertices $i$ and $j$, you get a modified combinatorial Laplacian. Taking the determinant of any minor of this matrix gives a modified Kirchhoff polynomial which is a weighted enumeration of the spanning forests of the graph, where each term is a monomial contains the variables for all the edges in a given forest $\mathcal{F}$ and the coefficient is $T(\mathcal{F}).$ So this polynomial spits out all the spanning forests including the empty one (times $n^{n-2}$) ,each of the spanning trees, and everything in between.