Linear algebraic techniques for weighted spanning tree enumeration
Steven Klee Matthew T. Stamps






Seattle University, Department of Mathematics 
 901 12th Avenue, Seattle, WA 98122, USA



Yale-NUS College, Division of Science 
 10 College Avenue West, #01-101 Singapore 138609


Weighted Spanning Tree Enumeration


Linear Algebraic Techniques for Weighted Spanning Tree Enumeration
    Steven Klee and Matthew T. Stamps
    
==================================================================




The weighted spanning tree enumerator of a graph G with weighted edges is the sum of the products of edge weights over all the spanning trees in G.  In the special case that all of the edge weights equal 1, the weighted spanning tree enumerator counts the number of spanning trees in G.  The Weighted Matrix-Tree Theorem asserts that the weighted spanning tree enumerator can be calculated from the determinant of a reduced weighted Laplacian matrix of G.  That determinant, however, is not always easy to compute.  In this paper, we show how two well-known results from linear algebra, the Matrix Determinant Lemma and the method of Schur complements, can be used to elegantly compute the weighted spanning tree enumerator for several families of graphs.














§ INTRODUCTION




In this paper, we restrict our attention to finite simple graphs.  We will assume each graph has a finite number of vertices and does not contain any loops or multiple edges. We will denote the vertex set and edge set of a graph G by V(G) and E(G), respectively.  A function ω: V(G) × V(G) →ℝ, whose values are denoted by ω_i,j for v_i,v_j ∈ V(G), is an edge weighting on G if ω_i,j = ω_j, i for all v_i, v_j ∈ V(G) and if ω_i,j = 0 for all {v_i,v_j}∉ E(G).  The weighted degree of a vertex v_i ∈ V(G) is the value 
    (v_i;ω) = ∑_v_j ∈ V(G)ω_i,j = ∑_v_j   :  {v_i,v_j}∈ E(G)ω_i,j.

For a matrix M, we will use M(i,j) to denote its entry in row i and column j and M_i,j to denote the submatrix of M obtained by crossing out its i^th row and j^th column. 

Let G be a graph whose edges are weighted by a function ω.  The weighted Laplacian matrix, L(G;ω), is a matrix whose rows and columns are indexed by the vertices of G and whose entries are given by

    L(G;ω)(i,j) = 
    (v_i;ω)     if  i = j, 
    
    -ω_i,j    if  i ≠ j.


 The weighted Laplacian matrix is singular because its rows sum to zero; however, its cofactors have a beautiful combinatorial interpretation in terms of spanning trees.  

[<cit.>]
Let G be a graph with V(G) = {v_1,…,v_n} and let ω be an edge weighting on G.  For any vertices v_i,v_j ∈ V(G), not necessarily distinct, 

    ∑_T ∈𝒮𝒯(G)∏_{v_k,v_ℓ}∈ E(T)ω_k,ℓ  = (-1)^i+j(L(G;ω)_i,j),

where 𝒮𝒯(G) is the set of all spanning trees of G.


The quantity on the left side of Equation (<ref>) is called the weighted spanning tree enumerator for the edge-weighted graph (G;ω), which we will denote by τ(G;ω). Note that when ω_k,ℓ = 1 for each edge in G, L(G;ω) is the ordinary Laplacian matrix and τ(G;ω) counts the number of spanning trees in G. Thus, the Weighted Matrix-Tree Theorem is a more general version of the commonly cited Matrix-Tree Theorem.  

As succinct as the Weighted Matrix-Tree Theorem is, computing the weighted spanning tree enumerator from the Laplacian matrix often requires algebraic insights (even for common families of graphs like complete graphs).  For instance, the choice of which row and column to remove can significantly impact the complexity of the resulting determinant. In this paper, we show how two elementary tools from linear algebra – the Matrix Determinant Lemma and the method of Schur complements –  can be used to elegantly compute the weighted spanning tree enumerator for several well-studied families of graphs without having to eliminate rows or columns.  While the results themselves are not new, we believe the technique is beautiful and worth recording.  Specifically, we give new proofs of the following results: 


  * the Cayley-Prüfer Theorem, which gives a formula for the weighted spanning tree enumerator for complete graphs <cit.>;

  * a generalization of the Cayley-Prüfer Theorem to weighted complete multipartite graphs, a result originally given by Clark <cit.>;

  * the weighted spanning tree enumerator for Ferrers graphs, a result originally given by Ehrenborg and van Willigenburg <cit.>; and

  * the weighted spanning tree enumerator for threshold graphs, a result originally given by Martin and Reiner <cit.>.


In all of these cases, the weights on the edges of each graph G have the form ω_i,j = x_ix_j for some indeterminates {x_i  :  v_i ∈ V(G)} so the weighted spanning tree enumerator can be viewed as the  polynomial 
    ∑_T ∈𝒮𝒯(G)∏_v_i ∈ V(G) x_i^_T(v_i)
 in these variables.  This form is essential because the weights can be encoded in a rank-one matrix that can be added to the weighted Laplacian matrix so that the resulting determinant can be understood with the help of the Matrix Determinant Lemma.  For Ferrers graphs and threshold graphs, we will see that this linear algebraic approach allows us to easily reduce the weighted spanning tree enumerator to the determinant of an upper triangular matrix.

The rest of the paper is structured as follows.  In Section <ref> we review the Matrix Determinant Lemma and Schur complement.  We then prove our main result, Lemma <ref> and immediately show how it can be used to give a quick proof of the Cayley Prüfer theorem, along with a generalization to complete multipartite graphs.  In Section <ref>, we use Lemma <ref> to calculate the weighted spanning tree enumerator for Ferrers graphs.  In Section <ref>, we use Lemma <ref> to calculate the weighted spanning tree enumerator for threshold graphs.  The arguments in Sections <ref> and <ref> may seem a bit lengthy, but that is simply because we have chosen to carefully describe the entries of several matrices at each step.  The proofs themselves use nothing more than elementary matrix multiplication.  Proofs of the unweighted versions of the results in this paper, which are especially concrete and concise, are presented in <cit.>.







§ TOOLS FROM LINEAR ALGEBRA




In this section, we review two well-known results in linear algebra and present our main result, Lemma <ref>, whose applicability we will demonstrate in subsequent sections of the paper.  The first linear algebraic result we require is the Matrix Determinant Lemma. Recall that the adjugate of an n × n matrix is the transpose of its n × n matrix of cofactors.


Let M be an n × n matrix and let  and  be column vectors in ℝ^n.  Then 
    (M+^T) = (M) + ^T(M).
  In particular, if M is invertible, then (M+^T) = (M)(1+^TM^-1).


A proof of the Matrix Determinant Lemma can be found in the textbook of Horn and Johnson <cit.>, where it is referred to as Cauchy's formula for the determinant of a rank-one perturbation.  The main ingredients in the proof are the fact that (·) is a multilinear operator on the rows of a matrix and the observation that ^T is a rank-one matrix. 

We are now ready to prove our main result.

 
Let G be a graph on vertex set V whose edges are weighted by a function ω. Let L be the weighted Laplacian matrix of G, and let 𝐚 = (a_i)_v_i ∈ V and 𝐛 = (b_i)_v_i ∈ V be column vectors in ℝ^V.  Then 
    (L + 𝐚𝐛^T) = (∑_v_i ∈ V a_i ) ·(∑_v_i ∈ V b_i ) ·τ(G;ω).




Let 1_V, V denote the |V| × |V| matrix of ones, and let 1_V denote the |V| × 1 vector of ones. By the Weighted Matrix-Tree Theorem, every cofactor of L equals τ(G;ω), so 
    (L) = τ(G;ω) 1_V, V =  τ(G;ω) 1_V 1_V^T.
 Therefore, by the Matrix Determinant Lemma, 

    (L + 𝐚𝐛^T)    =   (L) + 𝐛^T (L) 𝐚
       =    0 + 𝐛^T(τ(G;ω) 1_V 1_V^T)𝐚
       =   (𝐛^T1_V)( 1_V^T𝐚) ·τ(G;ω)
       =   (∑_v_i ∈ V a_i ) ·(∑_v_i ∈ V b_i ) ·τ(G;ω).



In the case that G is unweighted (meaning ω_ij = 1 for each edge) and =  = 1_V, this result simplifies to say (L+1_V, V) is equal to |V(G)|^2 times the number of spanning trees in G.  This result was originally given by Temperley <cit.>, who computed the determinant of L+^T via elementary row operations. 

As an immediate application of this result, we give a simple proof of the Cayley-Prüfer Theorem. 



Let x_1, …,x_n be indeterminates and suppose the edges of the complete graph K_n are weighted by ω_ij = x_ix_j.  Then the weighted spanning tree enumerator for K_n is given by 

    τ(K_n,ω)= x_1 ⋯ x_n (x_1+⋯+x_n)^n-2.




Let L denote the weighted Laplacian matrix of K_n.  Then the entries of L satisfy 

    L(i,j) = 
    x_i ·∑_k ≠ i x_k     if  i = j, 
    
     -x_ix_j     if  i ≠ j

Consider the vector 𝐱 = (x_1,…,x_n)^T.  Note that L + 𝐱𝐱^T is a diagonal matrix whose i^th diagonal entry is x_i(x_1+⋯+x_n).  Therefore, by Lemma <ref>, 



    (x_1+⋯+x_n)^2·τ(K_n,ω)     =   (L + 𝐱𝐱^T) 
       =   ∏_i=1^n x_i(x_1+⋯+x_n).




This technique can also be applied to calculate weighted spanning tree enumerators for complete multipartite graphs.  Let G be the complete multipartite graph K_n_1,…,n_k with its vertex set partitioned as V_1 ⊔⋯⊔ V_k.  Let n = n_1 + ⋯ + n_k and order the vertices of G so that v_1, …, v_n_1 are the vertices in V_1, v_n_1+1, …, v_n_1+n_2 are the vertices in V_2, and so on.  Clark <cit.> originally proved the following result. 

 
Let G be the complete multipartite graph with n vertices and k parts described above, let x_1, …, x_n be indeterminates, and suppose the edges of G are weighted by ω_i,j = x_ix_j.  Then the weighted spanning tree enumerator for G  is given by 

    τ(G,ω) = ( ∏_i=1^n x_i )  ·(∏_ℓ=1^k (∑_v_j ∉ V_ℓ x_j)^n_ℓ-1) ·( ∑_i=1^n x_i )^k-2.




Once again, let L denote the weighted Laplacian matrix of G, let 𝐱 = (x_1,…,x_n)^T, and consider L + 𝐱𝐱^T, which is a block diagonal matrix with blocks indexed by the sets V_1, …, V_k. For each 1 ≤ℓ≤ k, let 𝐱_ℓ be the n_ℓ× 1 vector of indeterminates corresponding to vertices in V_ℓ. In other words, 𝐱_ℓ is the orthogonal projection of 𝐱 onto the subspace spanned by vertices in V_ℓ. The ℓ^th diagonal block of L + 𝐱𝐱^T has the form D_ℓ + 𝐱_ℓ𝐱_ℓ^T, where D_ℓ is the diagonal matrix of weights corresponding to the vertices in V_ℓ.  Specifically, for a vertex v_i ∈ V_ℓ, the corresponding diagonal entry in D_ℓ is x_i ∑_v_j ∉ V_ℓ x_j. 

By the Matrix Determinant Lemma, 

    (D_ℓ + 𝐱_ℓ𝐱_ℓ^T)    =   (D_ℓ) ( 1 + 𝐱_ℓ^T D_ℓ^-1𝐱_ℓ) 
       (*)=   (D_ℓ) ( 1 + ∑_v_i ∈ V_ℓ x_i/∑_v_j ∉ V_ℓ x_j ) 
       =   (D_ℓ) ( ∑_i=1^n x_i/∑_v_j ∉ V_ℓ x_j) 
       =   (∏_v_i ∈ V_ℓx_i) (∑_j ∉ V_ℓx_j)^n_ℓ-1(∑_i=1^n x_i),

where the second equality (*) follows from the fact that D_ℓ^-1 can be written as the diagonal matrix of inverse weights x_i^-1 for v_i ∈ V_ℓ multiplied by (∑_v_j ∉ V_ℓx_j)^-1. The result now follows from Lemma <ref>, together with the fact that (L+𝐱𝐱^T) = ∏_ℓ=1^k (D_ℓ + 𝐱_ℓ𝐱_ℓ^T). 


Setting x_i = 1 for all 1 ≤ i ≤ n in Theorem <ref> yields the number of spanning trees in K_n_1,…,n_k, 
    n^k-2·∏_ℓ=1^k (n-n_ℓ)^n_ℓ-1,
 which has been reproved many times and is originally due to Lewis <cit.>.





 §.§ The Schur complement of a matrix




We conclude this section by briefly reviewing the Schur complement of a matrix. Later in this paper, there will be instances in which we partition the vertices of a graph into disjoint subsets as V(G) = V_1 ⊔ V_2.  In such instances, the Laplacian matrix of G can be decomposed into a block matrix of the form 
    ( [ A B; C D ]),
 where the first |V_1| rows and columns correspond to the vertices in V_1 and the last |V_2| rows and columns correspond to the vertices in V_2.  In this case, A and D are square matrices of sizes |V_1| × |V_1| and |V_2| × |V_2| respectively. Now suppose M is any square matrix that can be decomposed into blocks A, B, C, D as above with A and D square.  If D is invertible, then the Schur complement of D in M is defined as M/D:= A- BD^-1C.  A fundamental reason for using Schur complements is the following result (see <cit.>).

 
Let M be a square matrix decomposed into blocks A, B, C, D as above with A and D square and D invertible.  Then 
    (M) = (D) ·(A-BD^-1C).



When M = [ a b; c d ] is a 2 × 2 matrix and d ≠ 0, Lemma <ref> simply says that (M) = d (a - b ·1/d· c), which is just an alternate way of writing the familiar formula for the determinant of a 2 × 2 matrix. 








§ WEIGHTED SPANNING TREE ENUMERATION FOR FERRERS GRAPHS
 


In this section, we demonstrate the applicability of Lemmas <ref> and <ref> for calculating the weighted spanning tree enumerators for Ferrers graphs.

A partition of a positive integer z is an ordered list of positive integers whose sum is z.  For example, (4,4,3,2,1) is a partition of 14.  We write λ = (λ_1, …, λ_m) to denote the parts of the partition λ.  To any partition, there is an associated bipartite Ferrers diagram, which is a stack of left-justified boxes with λ_1 boxes in the first row, λ_2 boxes in the second row, and so on. To any Ferrers diagram there is an associated Ferrers graph, whose vertices are indexed by the rows and columns of the Ferrers diagram with an edge if there is a box in the corresponding position.  The Ferrers diagram and corresponding Ferrers graph associated to the partition λ = (4,4,3,2,1) are shown in Figure <ref>.

Equivalently, a Ferrers graph is a bipartite graph G whose vertices can be partitioned as R ⊔ C with R = {r_1,…,r_m} (corresponding to the rows of a Ferrers diagram) and C = {c_1,…,c_n} (corresponding to the columns of a Ferrers diagram) such that 


  * if {r_k,c_ℓ}∈ E(G), then {r_i,c_j}∈ E(G) for any i ≤ k and j ≤ℓ, and

  * {r_1,c_n}∈ E(G) and {r_m,c_1}∈ E(G).


Suppose the edges of a Ferrers graph are weighted by ω_r_i,c_j = x_iy_j.  Ehrenborg and van Willigenburg <cit.> used the theory of electrical networks to give a closed formula for the weighted spanning tree enumerator in this case. The result is most simply stated using the correspondence between Ferrers graphs and partitions.  If λ = (λ_1, λ_2, …, λ_m) is a partition, then its conjugate partition is λ' = (λ_1', λ_2, …, λ_n'), where λ_j' counts the number of parts λ_i with λ_i ≥ j and n = λ_1 is the size of the largest part in λ.  In terms of Ferrers diagrams, λ_i counts the number of boxes in the i^th row and λ'_j counts the number of boxes in the j^th column.


Let G be a Ferrers graph whose vertices are partitioned as V(G) = R ⊔ C with |R| = m and |C| = n.  Suppose G corresponds to the partition λ = (λ_1, …, λ_m) whose conjugate partition is λ' = (λ_1', λ_2', …, λ_n'). Let x_1,…,x_m, y_1,…,y_n be indeterminates and suppose the edges of G are weighted by ω_i,j = x_iy_j for each {r_i,c_j}∈ E(G).  Then 

    τ(G; ω) = (∏_i = 1^m x_i) ·(∏_j = 1^n y_j) ·( ∏_i=2^m(∑_j=1^λ_iy_j)) ·(∏_j=2^n(∑_i=1^λ'_jx_i)).





Let L be the weighted Laplacian matrix of G, let 𝐲 be the (m+n) × 1 vector given by 𝐲(r_i) = 0 for all 1 ≤ i ≤ m and 𝐲(c_j) = y_j for all 1 ≤ j ≤ n, and let 𝐱 be the (m+n) × 1 vector given by 𝐱(r_i) = x_i for all 1 ≤ i ≤ m and 𝐱(c_j) = 0 for all 1 ≤ j ≤ n.  (One can think of 𝐲 as a weighted indicator vector for C in ℝ^V and 𝐱 as a weighted indicator vector for R in ℝ^V.)  The diagonal entries of L are x_i · (y_1+⋯+y_λ_i) for each vertex r_i ∈ R and y_j · (x_1+⋯+x_λ'_j) for each vertex c_j ∈ C.  We decompose M:=L + 𝐲𝐱^T as a block matrix 

    M = [  D_R    B; B^op  D_C ],
 where 


  * D_R is the diagonal m × m matrix of weighted degrees of vertices in R,

  * D_C is the diagonal n × n matrix of weighted degrees of vertices in C,

  * B is the m × n matrix with entries -x_iy_j if {r_i,c_j}∈ E(G) and 0 otherwise, and 

  * B^op = B^T + (y_1,…,y_n)^T(x_1,…,x_m) is the n × m matrix with entries x_iy_j if {r_i,c_j}∉ E(G) and 0 otherwise. 


Let S:= D_R-BD_C^-1B^op be the Schur complement of the block D_C in M. The entries of S can be explicitly computed as follows: Consider rows r_i and r_j that are not necessarily distinct.  The entry (BD_C^-1B^op)(r_i,r_j) is equal to the inner product of the r_i-row of B with the r_j-column of D_C^-1B^op.  This entry equals 
    -∑x_ix_jy_k^2/y_k(x_1+⋯+x_λ'_k),
 where the sum is over all vertices c_k such that {r_i,c_k}∈ E(G) and {r_j,c_k}∉ E(G).  In other words, the sum is over all c_k ∈ N(r_i) ∖ N(r_j), where N(·) denotes the neighborhood of a vertex. 
Because G is a Ferrers graph, N(r_1) ⊇ N(r_2) ⊇⋯⊇ N(r_m).  This means (BD_C^-1B^op)(r_i,r_j) = 0 when i ≥ j.  Thus S is upper triangular and its diagonal entries are the same as those in D_R.  

The result now follows from Lemmas <ref> and <ref> because 

    ∑_v ∈ V(G)𝐲(v)    =   
    ∑_j=1^n y_j = ∑_j=1^λ_1 y_j, 
    ∑_v ∈ V(G)𝐱(v)    =   
    ∑_i=1^m x_i = ∑_i=1^λ'_1 x_i, 
    (D_C)    =   ∏_j=1^n (y_j ∑_i=1^λ'_jx_i), 
    (S) = (D_R)    =   ∏_i=1^m (x_i∑_j=1^λ_i y_j),  and
    (L+𝐲𝐱^T)    =   (D_C) (S).







§ WEIGHTED SPANNING TREE ENUMERATION FOR THRESHOLD GRAPHS
 



In this section, we demonstrate the applicability of Lemmas <ref> and <ref> for calculating the spanning tree enumerators of threshold graphs.

Threshold graphs have many equivalent definitions <cit.>, but the following one will be most relevant for us:  A graph G on n vertices is a threshold graph if its vertices can be ordered v_1,…,v_n in such a way that if {v_j,v_ℓ}∈ E(G) for some 1 ≤ j < ℓ≤ n, then {v_i,v_ℓ}∈ E(G) for all i < j and {v_j,v_k}∈ E(G) for all k < ℓ. An example threshold graph is illustrated in Figure <ref>.

 

If G is a threshold graph, we consider a special vertex v_t, where t is the largest index such that {v_i,v_j}∈ E(G) for all 1 ≤ i < j ≤ t. This special vertex in the graph in Figure <ref> is t = 4.  For readers who are familiar with the definition that threshold graphs are defined starting from an initial vertex and inductively adding dominating or isolated vertices, v_t is the initial vertex, the vertices v_1,…,v_t-1 are the dominating vertices in G (where v_t-1 is the first dominating vertex, v_t-2 the second, and so on), and v_t+1, …, v_n are the isolated vertices (where v_t+1 is the first isolated vertex, v_t+2 the second, and so on).  Because the vertex degrees in a threshold graph weakly decrease in order, (v_1) ≥(v_2) ≥⋯≥(v_n), the degree sequence of a threshold graph is a partition.  

Martin and Reiner <cit.> consider a weighting on the edges of a threshold graph in which ω_i,j = x_min(i,j)y_max(i,j) for indeterminates x_1,…,x_n,y_1,…,y_n. Because of the natural ordering on the vertices of a threshold graph, the weight of a spanning tree T has a nice interpretation as 
    ∏_i=1^n x_i^_T(v_i) y_i^_T(v_i),
 where the edges of G are oriented from the higher indexed vertex to the lower indexed vertex. With this, Martin and Reiner give the following result <cit.>. 


Let G be a connected threshold graph with V(G) = {v_1,…,v_n} and degree sequence δ = (δ_1,…,δ_n), let v_t be the special vertex defined above, and consider the weighting of edges in G given by ω_i,j = x_min(i,j)y_max(i,j) with indeterminates x_1,…,x_n,y_1,…,y_n.  Then 

    τ(G;ω) = ∑_T ∈𝒮𝒯(G)∏_i=1^n x_i^_T(v_i)y_i^_T(v_i) = x_1 (∏_i=t^n y_i) (∏_j=2^t-1 f_j) ( ∏_j=t+1^n g_j ) ,

where 
    f_j := y_j∑_i=1^jx_i + x_j ∑_k=j+1^1+δ_jy_k      and      g_j := ∑_i=1^δ_jx_i.



Before we prove this theorem, a few comments are in order.  First, setting x_i = y_i = 1 for 1 ≤ i ≤ n tells us that the number of spanning trees in a connected threshold graph G is given by 

    ∏_i=2^t-1((v_i)+1) ∏_i=t+1^n (v_i),

a result that was originally shown by Merris <cit.>. In the particular case that t=n, G is the complete graph on n vertices and we recover Cayley's formula: the number of spanning trees in K_n is ∏_i=2^n-1n = n^n-2.  Moreover, when t=n and y_i = x_i for all i, we get f_i = x_i(x_1 + ⋯ + x_n) for all i and recover the Cayley-Prüfer Theorem. 

In their paper, Martin and Reiner describe this formula in terms of an index s, which is the side length of the Durfree square in the partition δ.  To translate between their formula and ours, substitute s = t-1.


Let L be the weighted Laplacian matrix of G.  We can partition L as a block matrix of the form 

    L = [   A   B; B^T   D ],

where the rows and columns of A are indexed by vertices v_1, …, v_t and the rows and columns of D are indexed by vertices v_t+1,…,v_n.

Consider the n × 1 column vectors 𝐲 = (y_1,…,y_n)^T and 𝐱 = (x_1,…,x_t,0,…,0)^T. Because the entry in row i and column j of 𝐲𝐱^T is x_jy_i if 1 ≤ j ≤ t and zero otherwise, L+𝐲𝐱^T has an analogous partition into blocks of the form

    L+𝐲𝐱^T = [   A'    B; B^op    D ].
  
As in the proof of Theorem <ref>, we can explicitly describe the entries within each block and then compute (L+𝐲𝐱^T) by taking the Schur complement of block D.  
The j^th diagonal entry in block A is 
    A(j,j) = ∑_i=1^j-1 x_iy_j + ∑_k=j+1^1+δ_jx_jy_k = y_j ∑_i=1^j-1x_i + x_j ∑_k=j+1^1+δ_jy_k.
 This is because vertex v_j has degree δ_j and, since G is threshold, its neighbors are the first δ_j vertices in order other than v_j itself; the weight of an edge {v_i,v_j} with i < j is x_iy_j; and the weight of an edge {v_j,v_k} with j < k is x_jy_k. The off-diagonal entries in A are A(i,j) = -x_iy_j if i<j and A(i,j) = -x_jy_i if i>j.  Therefore, when adding 𝐲𝐱^T to L, the entries below the diagonal of A vanish.  Thus, A' is upper triangular with diagonal entries A'(j,j) = x_jy_j + A(j,j) = f_j.  

Block B records incidences among vertices in {v_1,…,v_t} and {v_t+1,…,v_n}.  Since the rows in B are indexed by the former set and the columns in B are indexed by the latter, the entries in B are given by B(i,j) = -x_iy_j if {v_i,v_j}∈ E(G) and zero otherwise. Because of our choice of 𝐲 and 𝐱, B^op is the (n-t) × t matrix 
    B^op = B^T + (y_t+1,…,y_n)^T(x_1,…,x_t).
  Therefore, B^op(i,j) = x_jy_i if {v_i,v_j}∉ E(G) and zero otherwise.  
 
 Finally, because the first t vertices of G span a clique and the first t+1 vertices do not, we see that {v_t,v_t+1}∉ E(G).  This implies that {v_i,v_j}∉ E(G) for all t ≤ i,j ≤ n.  Therefore, D is a diagonal matrix with diagonal entries 
    D(j,j) = y_j ∑_i=1^δ_j x_i = y_jg_j
 for t+1 ≤ j ≤ n.  
 





As in the proof of Theorem <ref>, for any 1 ≤ i,j ≤ t, the entries of (BD^-1B^op)(i,j) can be written as a weighted sum over vertices v_k ∈ N(v_i) ∖ N(v_j) such that t+1 ≤ k ≤ n. Because G is threshold, this set of vertices is empty whenever i ≥ j, so BD^-1B^op is strictly upper triangular.  Because A' is upper triangular, this means A'-BD^-1B^op is upper triangular and its diagonal is the same as the diagonal of A'. Therefore, by Lemma <ref>, 
 
 
    (∑_i=1^n y_i) ·(∑_i=1^t x_i) ·τ(G;ω)    =   (L + 𝐲𝐱^T)
       =   (D) (A'-BD^-1B^op) 
       =   (∏_j=t+1^n y_jg_j) (∏_j=1^t f_j )

 
Since G is connected, v_n is not isolated, which means {v_1,v_n}∈ E(G).  Because G is threshold, this means v_1 is adjacent to every vertex in G, so 
    f_1 = x_1y_1 + x_1 ∑_i=2^n y_i = x_1∑_i=1^n y_i.
 Similarly, because v_t is only adjacent to v_1, …, v_t-1, δ_t = t-1 and f_t = y_t∑_i=1^t x_i. The result follows. 






§ ACKNOWLEDGMENTS




Steven Klee's research was supported by NSF grant DMS-1600048.  Matthew Stamps is grateful to Isabella Novik and the Department of Mathematics at the University of Washington for hosting him during the time this research was conducted.



plain


