17 votes
Accepted

Is there a natural relationship between OEIS A127670 and Cayley's tree formula?

Yes there is a connection. While $n^{n-2}$ counts the number of vertex labeled trees on $n$ vertices, the expression $2^n(n+1)^{n-2}$ counts the number of edge labeled trees on $n$ edges. There is a ...
Gjergji Zaimi's user avatar
15 votes

Could someone explain the proof of this formula clearly? I got the wrong values for spanning trees with this formula and with Cayley's formula

The problem is that for a complete graph, $\mu_{n-1} \leq \delta$ is wrong, and thus $f(\delta) < f(\mu_{n+1})$. This can be fixed by adding a special case for the complete graph (for other graphs $...
Command Master's user avatar
15 votes
Accepted

History of deletion-contraction formula

This seems to have first been observed in Brooks, R.L.; Smith, C.A.B.; Stone, A.H.; Tutte, W.T., The dissection of rectangles into squares, Duke Math. J. 7, 312-340 (1940). ZBL0024.16501. See ...
Ian Agol's user avatar
  • 66.8k
13 votes
Accepted

Create a graph with a specified number of spanning trees

A $k$-cycle works if $k>2$. For $k=1$ any tree works. I don't think $k=2$ is possible unless you allow double edges: if the graph is not a tree then it has an $m$-cycle $C$ for some $m>2$; ...
Noam D. Elkies's user avatar
11 votes
Accepted

Random sample of spanning trees

One approach is to generate $k$ random Prüfer sequences and then convert each sequence into a tree. It is also well-known that performing a random walk on $K_n$ will generate a random spanning tree ...
Tony Huynh's user avatar
  • 31.5k
9 votes
Accepted

Counting spanning trees of a planar graph

The determinant of matrices whose support corresponds to incidence matrices of planar graphs (this includes the Laplacian matrix of a planar graph, or more precisely its cofactors) can be calculated ...
Gjergji Zaimi's user avatar
8 votes

Class numbers of functions fields and spanning trees

I think you remembered correctly except that it should be the modular curve $X_0(N)$. Note that $N$ is prime here. The Eichler-Shimura relation says the eigenvalues of Frobenius on the Tate module of ...
Will Sawin's user avatar
  • 135k
8 votes

History of deletion-contraction formula

Not exactly a reference, but I found some discussion of this formula in Bill Tutte's graph-theoretic memoirs, Graph Theory as I Have Known it (Oxford, 1998). In Chapter 5 ("Algebra in Graph ...
Noam Zeilberger's user avatar
7 votes

Create a graph with a specified number of spanning trees

If $G_1$ and $G_2$ are graphs let $G_1 \vee G_2$ denote their wedge sum. That is, $G_1 \vee G_2$ is obtained by taking the one-point union of $G_1$ and $G_2$. It will not matter what vertices we ...
John Machacek's user avatar
5 votes
Accepted

Spanning tree minimizing $F_T = \sum_{i = 1}^{|V| - 1|} (w(e_i) - P_T)^2$

The problem is equivalent to finding $\min_{e_i, \lambda} \sum (w(e_i) - \lambda)^2$, where $\lambda$ is a free real parameter subject to optimization as well as the edges of a spanning tree. Indeed, ...
Mikhail Tikhomirov's user avatar
5 votes
Accepted

Minimum euclidean spanning tree in n dimensional space

The best you can hope for is $O(n \log n)$ plus a term dependent upon accuracy, for finding an approximate Euclidean MST. The fastest known exact algorithm is just a hair better than quadratic, $O(n^2)...
Joseph O'Rourke's user avatar
5 votes
Accepted

Is there a formula for the number of trees with this extra condition?

If the trees are labelled, then each tree satisfying the condition corresponds to exactly one spanning tree of the bipartite graph $K_{n_1,n_2}$. Therefore the answer is the number of spanning trees ...
Yto's user avatar
  • 148
4 votes
Accepted

Existence of connected set with large edge boundary

If I am not mistaken, then the following recursive construction disproves statement A: Let $G_1$ consist of a $K_8$ and an additional vertex $r_1$ connected to half of the vertices of this $K_8$ For $...
Florian Lehner's user avatar
4 votes

Existence of connected set with large edge boundary

I think I have a counter-example to Statement B: Start with a $K_r$ and connect every vertex to one vertex of a new $K_4$. This is the graph $\Gamma=(V,E)$, which has $5r$ vertices. Any set $S\subset ...
AMLimbach's user avatar
3 votes
Accepted

Relation between Kirchhoff's Circuital law and Matrix tree Theorem

Chapter II (pages 12 and following) of Combinatorics of Electrical Networks gives a linear algebra derivation of Kirchhoff's theorem from the circuit laws of Ohm and Kirchhoff.
Carlo Beenakker's user avatar
3 votes
Accepted

Property of the spanning tree with minimal leaves

If I am not mistaken, and if I understand you correctly, it seems to me that you are right. The following statement is true. Let $G$ be a connected graph and $T$ be the spanning tree with the ...
kabenyuk's user avatar
  • 673
3 votes

Transfer-impedance matrix for edge correlations in random spanning tree

For question 3, the analogue of the transfer-impedance matrix for a linear matroid (more precisely, a linear matroid plus a choice of matrix $M$, whose rows represent it) is treated in Lyons's paper ...
j.c.'s user avatar
  • 13.5k
2 votes
Accepted

Spanning tree with sufficient transformation

I assume that by a transition you mean adding one edge and removing another. Then it seems that a simple algorithm works: Add an edge from the new tree. This will create a cycle so just remove one ...
ericf's user avatar
  • 614
2 votes

Even parking functions and spanning trees of complete bipartite graphs

This is far from an answer, but only a possible first part of such a bijection. (There were two plainly wrong bijection parts in the first version that cannot be fixed.) The bijection between ...
Christian Stump's user avatar
2 votes

Hu-Gomory trees and Optimum Communication tree

Taking the definition of a cut-tree from the linked paper (page 190, just before Lemma 1), or equivalently, the definition of a Gomory-Hu tree from Wikipedia, it appears that the answer in the linked ...
Thomas Kalinowski's user avatar
2 votes
Accepted

Calculating number of vertex-pairs with separate common ancestor

It takes only addition to count the distinct pairs where one is the ancestor of another. Couldn’t you just subtract that from the total number of pairs?
Aaron Meyerowitz's user avatar
2 votes
Accepted

Counting spanning trees of $K_{b+1,w+1}$ with certain properties or calculating a combinatorial sum

This should follow from Kirchoff's formula (and apologies in advance if I made a calculation error below). What you're asking for is the number of spanning trees that can be obtained by contracting ...
Jason Gaitonde's user avatar
2 votes
Accepted

Minimum spanning tree and projection

I think you mean that $y$ is the characteristic vector. That is, $y_{ij}=1$ if edge $(i,j)$ is in the forest and $0$ otherwise. Let $E$ be the edge set of $G$. Given $x$, you want to find $y$ to ...
RobPratt's user avatar
  • 5,159
2 votes
Accepted

Relation of MSTs in the Euclidean plane to Delaunay triangulations

It cannot be for any planar triangulation. Say we have a triangle with vertices $x, y, z$ and $xy$ is the longest edge. Consider a run of Prim’s MST algorithm which at each step adds an edge to a ...
Izaak Meckler's user avatar
1 vote

Random sample of spanning trees

There is an algorithm for unranking and ranking spanning trees due to Colbourn, Day and Nel which is described in https://www.sciencedirect.com/science/article/abs/pii/0196677489900163 You can compute ...
Gordon Royle's user avatar
  • 12.3k
1 vote

Existence of connected set with large edge boundary

Reduction of Statement A to Statement B. Let $S$ be as in statement B. Let, at first, $S'=S$. Do the following repeatedly until you cannot: include in $S'$ an element of $V\setminus S'$ having at ...
H A Helfgott's user avatar
  • 19.3k
1 vote

Two independent spanning trees of $2$-connected graph

Let's use a new concept oriented path in a cycle $C$ or an open ear $P_k$. In $C$: Label the vertices in $C$ in clockwise direction by $u,v_1,\cdots,v_n$. Then the clockwise-oriented path of $C$ ($...
okw1124's user avatar
  • 331
1 vote
Accepted

Two independent spanning trees of $2$-connected graph

Yes, this is true. We will prove the following stronger lemma. Lemma. Let $G$ be a $2$-connected graph and $u \in V(G)$. Then $G$ contains two spannings trees $T_1$ and $T_2$ such that for all $a,b \...
Tony Huynh's user avatar
  • 31.5k
1 vote

Calculating number of vertex-pairs with separate common ancestor

In the article Sums of powers of the degrees of a graph one finds for the sum of squared vertex degrees the formula $\sum_2(G)\le e\left(\frac{e}{n-1}+n-2\right);\ e:=\mathrm{card}(E),\ n := \mathrm{...
Manfred Weis's user avatar
  • 12.6k
1 vote

Spanning tree minimizing $F_T = \sum_{i = 1}^{|V| - 1|} (w(e_i) - P_T)^2$

It seems that Mikhail's nice answer will lead to a solution of the opening poster's problem. I would like to make one little precise point: Even in situations where the 'linear' problem of '...
Peter Heinig's user avatar
  • 6,001

Only top scored, non community-wiki answers of a minimum length are eligible