pith. sign in

arxiv: 1907.07376 · v1 · pith:QIQOAK4Znew · submitted 2019-07-17 · 🧮 math.CO

Formulas counting spanning trees in line graphs and their extensions

Fengming Dong This is my paper

Pith reviewed 2026-05-24 20:30 UTC · model grok-4.3

classification 🧮 math.CO
keywords spanning treesline graphsmiddle graphsclique cut-setsmultigraphsacyclic subgraphs
0
0 comments X

The pith

A closed-form formula counts spanning trees containing any given edge set M when M is acyclic and G minus M has only complete components.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes an explicit formula for the number of spanning trees in a connected multigraph that must include every edge from a chosen subset M. The formula holds precisely when the edges in M form no cycle and deleting them leaves only complete graphs as components. This condition directly produces counting formulas for all spanning trees in the line graph and the middle graph of any graph. The same result yields a factorization of the spanning tree count in any graph that has a clique serving as a cut-set, mirroring a known factorization property of the chromatic polynomial.

Core claim

For any connected multigraph G=(V,E) and any M⊆E such that M induces an acyclic subgraph and G-M has only complete components, a formula for τ_G(M) is obtained, where τ_G(M) counts spanning trees containing all edges in M. Applying this yields formulas for spanning trees in line graphs and middle graphs of arbitrary graphs, and shows that the spanning tree count factors when a clique is a cut-set, analogous to the chromatic polynomial.

What carries the argument

The explicit formula for τ_G(M) under the conditions that M induces an acyclic subgraph and components of G-M are complete graphs.

If this is right

  • Formulas for the number of spanning trees in the line graph of any graph follow immediately.
  • Formulas for the number of spanning trees in the middle graph of any graph follow immediately.
  • The spanning tree count of any connected graph factors when a clique acts as a cut-set, in direct analogy with the chromatic polynomial factorization.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The factorization result suggests recursive computation of spanning tree counts by repeatedly splitting along clique cut-sets.
  • The same conditions on M may permit explicit formulas for spanning trees in additional graph constructions such as total graphs.

Load-bearing premise

The stated conditions on M (acyclicity and completeness of components after removal) are sufficient to produce an explicit closed-form expression.

What would settle it

A concrete counterexample consisting of a connected multigraph G and edge set M satisfying the acyclicity and completeness conditions, yet where the stated formula fails to equal the actual number of spanning trees containing M.

Figures

Figures reproduced from arXiv: 1907.07376 by Fengming Dong.

Figure 1
Figure 1. Figure 1: Graph G ⋆ W, where G[W] has 3 components Lemma 2.2 Let W ⊆ E such that G[W] is a forest. For any W0 ⊆ W, τG(W) = τG⋆W (W′ ) = τG⋆W−W0 (W′ ), (2.1) where W′ = E(G ⋆ W) − E(G). 5 [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: EG(Vi , Vj ) = ∅ for all 1 ≤ i < j ≤ k and each component of G[M] is a star with a center in V0 3 Contracting a clique U Let U be a clique of a connected graph G = (V, E). In Subsection 3.1, we will deduce a formula for τG(W) in the case that G[W] is a forest, where W = E − E(G[U]). Let G •U denote the graph G/G[U]. In Subsection 3.2, we will give a relation between τG(M ∪ N) and τG•U (N), where M = EG(U) … view at source ↗
Figure 3
Figure 3. Figure 3: Each Fi is a star with a center in V − U independent set of G, then each Fi is a star with a center in V − U and E(Fi) ⊆ EG(U), implying that the claim holds by Claim 1. Now assume that V − U is not independent in G, i.e., E0 = E(G − U) 6= ∅. Since each component Fi is a star with a center in V − U, each edge e ∈ E0 is incident with two 8 [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: G[M ∪ N] is forest with t components F1, · · · , Ft Assume that N = E(G − U) and G[M ∪ N] is a forest with components F1, F2, · · · , Ft , as shown in [PITH_FULL_IMAGE:figures/full_fig_p010_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: G − V0 consists of k cliques and G[M] consists of stars with centers in V0 Let Mi = EG(Vi , V0) for all i = 1, 2, · · · , k. Then M = EG(V0) = S 1≤i≤k Mi . In this section, our main purpose is to apply Theorem 3.1 to find an expression for τG(M ∪ N) for any N ⊆ E(G[V0]). Applying this result, we are able to get an expression of τG(R ∪ N) for any R ⊆ M. 4.1 τG(M ∪ N) for N ⊆ E(G[V0]) Let U = V1 ∪ · · · ∪ Vk… view at source ↗
Figure 6
Figure 6. Figure 6: Graphs G and Gv⊳E0 , where E0 = {e1, e2, · · · , es} For any subgraph G0 of G, let G ⋄ G0 be the graph below: G ⋄ G0 = (· · ·((Gv1⊳E1 )v2⊳E2 )· · ·)vr⊳Er , where v1, v2, · · · , vr are those vertices in G0 with EG(vi) 6= EG0 (vi) and Ei = EG0 (vi). Clearly, G0 is the subgraph of G ⋄ G0 induced by V (G0) and the edges in E(G ⋄ G0) − E(G) form a matching of G ⋄ G0. An example is shown in [PITH_FULL_IMAGE:fi… view at source ↗
Figure 7
Figure 7. Figure 7: Graphs G and G ⋄ G0 For a family S = {E1, E2, · · · , Ek} of pairwise disjoint subsets of E(G), let G⋄S denote the following graph obtained by a sequence of ⋄-operations on subgraphs G[E1], G[E2], · · · , G[Ek]: (· · ·((G ⋄ G[E1]) ⋄ G[E2])· · ·) ⋄ G[Ek]. (5.2) Note that G ⋄ S is irrelevant to the order of E1, E2, · · · , Ek and (G ⋄ S)/W ∼= G, where W = E(G ⋄ S) − E(G). An example of G ⋄ S is shown in [PI… view at source ↗
Figure 8
Figure 8. Figure 8: Graphs G and G ⋄ S Assume that V (G) = {v1, v2, · · · , vn}. By the above definition, if S = {E1, E2, · · · , Ek} is 19 [PITH_FULL_IMAGE:figures/full_fig_p019_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: , then, for any W ⊆ E − E(G[U]), τG(W) = τG[U∪S1](W1) · τG[U∪S2](W2) |U| |U|−2 , (6.2) where Wi = W ∩ E(G[U ∪ Si ]). U S1 S2 s s s s s s s s s s s s . . . . . . ❤❤❤❤ ❤❤❤ [PITH_FULL_IMAGE:figures/full_fig_p022_9.png] view at source ↗
read the original abstract

For any connected multigraph $G=(V,E)$ and any $M\subseteq E$, if $M$ induces an acyclic subgraph of $G$ and removing all edges in $M$ yields a subgraph of $G$ whose components are complete graphs, a formula for $\tau_G(M)$ is obtained, where $\tau_G(M)$ is the number of spanning trees in $G$ which contain all edges in $M$. Applying this result, we can easily obtain a formula for the number of spanning trees in the line graph or the middle graph of an arbitrary graph. Applying this result, we also show that for any connected graph $G$ with a clique $U$ which is a cut-set of $G$, the number of spanning trees in $G$ has a factorization which is analogous to a property of the chromatic polynomial of $G$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 1 minor

Summary. The manuscript claims that for any connected multigraph G=(V,E) and M⊆E such that the subgraph induced by M is acyclic and every component of G-M is a complete graph, an explicit formula for τ_G(M) (the number of spanning trees of G containing all edges of M) can be derived. The derivation proceeds by contracting the complete components of G-M and applying the matrix-tree theorem to the resulting multigraph; acyclicity of M ensures the edges form a forest compatible with the components. The result is applied to obtain formulas for the number of spanning trees in the line graph and middle graph of an arbitrary graph, and to establish a factorization of the spanning-tree count in any connected graph possessing a clique cut-set, analogous to a known factorization of the chromatic polynomial.

Significance. If the central derivation holds, the paper supplies a parameter-free combinatorial tool that yields closed-form expressions for spanning-tree counts under explicit structural hypotheses on M. This directly produces new formulas for line graphs and middle graphs and a factorization property for graphs with clique cut-sets. The argument relies on standard contraction plus the matrix-tree theorem, with no invented entities or fitted parameters, and the applications follow by direct substitution of suitable M. These features make the result a useful addition to the literature on explicit spanning-tree enumeration.

minor comments (1)
  1. [Abstract] Abstract: the statement that 'a formula for τ_G(M) is obtained' is accurate but does not indicate the form of the formula (e.g., product over component sizes or determinant expression); a single sentence previewing the expression would improve readability without lengthening the abstract.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of the manuscript, for recognizing the utility of the central derivation, and for recommending acceptance without major comments.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained via matrix-tree theorem

full rationale

The paper states an explicit combinatorial condition on M (acyclicity plus complete components in G-M) and derives a closed-form count for spanning trees containing M by contracting those components and invoking the standard matrix-tree theorem on the contracted multigraph. This step is independent of the target formula and does not reduce to a self-definition, fitted parameter, or self-citation chain. Applications to line graphs and clique cut-sets are obtained by direct substitution of suitable M sets, again without circular reduction. No load-bearing premise relies on prior work by the same author that itself assumes the result.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Review performed on abstract only; the claimed formula rests on standard definitions of spanning trees, acyclicity, and complete graphs together with the two explicit conditions on M. No free parameters, invented entities, or non-standard axioms are visible in the abstract.

axioms (2)
  • standard math Spanning trees are acyclic connected spanning subgraphs; their number τ_G(M) counts those containing every edge of M.
    Invoked implicitly when defining τ_G(M).
  • domain assumption Removing an acyclic edge set M from G leaves a graph whose components are complete graphs.
    This is the explicit hypothesis under which the formula is stated.

pith-pipeline@v0.9.0 · 5663 in / 1327 out tokens · 20899 ms · 2026-05-24T20:30:38.785076+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

  1. [1]

    Aigner and G

    M. Aigner and G. Ziegler, Proofs from The Book , Fourth edition. Springer-Verlag, Berlin, 2010

    work page 2010

  2. [2]

    Brylawski and J.G

    T.H. Brylawski and J.G. Oxley, The Tutte polynomial and its applicat ions, in Matroid Applications, N. White, ed., Cambridge Univ. Press, 1992, pp. 123-225

    work page 1992

  3. [3]

    H. Y. Chen, F. J. Zhang, The critical group of a clique-inserted g raph, Discrete Math. 319 (2014), 24-32

    work page 2014

  4. [4]

    Dong, K.M

    F.M. Dong, K.M. Koh and K.L. Teo, Chromatic Polynomials and Chromaticity of Graphs, World Scientific, Singapore, 2005

    work page 2005

  5. [5]

    Dong and W.G

    F.M. Dong and W.G. Yan, Expression for the Number of Spanning Tr ees of Line Graphs of Arbitrary Connected Graphs, J. Graph Theory 85 (2017), 74-93

    work page 2017

  6. [6]

    J. A. Ellis-Monaghan and C. Merino, Graph Polynomials and Their App lications I: The Tutte Polynomial, in Structural Analysis of Complex Networks , M. Dehmer, Ed., Springer, 2011, pp. 219-255

    work page 2011

  7. [7]

    Lov´ asz, Combinatorial Problems and Exercises (second edition), North-Holland, Amsterdam, 1993

    L. Lov´ asz, Combinatorial Problems and Exercises (second edition), North-Holland, Amsterdam, 1993

    work page 1993

  8. [8]

    Macdonald, Symmetric functions and Hall polynomials (second edition), Claren- don Press, Oxford University Press, 1995

    I.G. Macdonald, Symmetric functions and Hall polynomials (second edition), Claren- don Press, Oxford University Press, 1995. 25

    work page 1995

  9. [9]

    Mohar, The Laplacian Spectrum of Graphs, in Graph Theory, Combinatorics, and Applications 2, Y

    B. Mohar, The Laplacian Spectrum of Graphs, in Graph Theory, Combinatorics, and Applications 2, Y. Alavi, G. Chartrand, O. R. Oellermann, and A. J. Schwenk, ed., Wiley, New York, 1991, pp. 871-898

    work page 1991

  10. [10]

    J. W. Moon, A tree counting problem, The annals of Mathematical Statistics 39 (1968), 242-245

    work page 1968

  11. [11]

    J. W. Moon, Various proofs of Cayley’s formula for counting tre es, A Seminar on Graph Theory. F. Harary, ed. Holt, Boston, 1967, 70-78

    work page 1967

  12. [12]

    J. W. Moon, On the second moment of the complexity of a graph, Mathematika 11 (1964), 95-98

    work page 1964

  13. [13]

    Read, An introduction to chromatic polynomials, J

    R.C. Read, An introduction to chromatic polynomials, J. Combin. Theory 4 (1968), 52-71

    work page 1968

  14. [14]

    Sato, Zeta functions and complexities of a semiregular bipart ite graph and its line graph, Discrete Math

    I. Sato, Zeta functions and complexities of a semiregular bipart ite graph and its line graph, Discrete Math. 307 (2007), 237-245

    work page 2007

  15. [15]

    Vahovskii, On the characteristic numbers of incidence matr ices for non-singular graphs, Sibirsk

    E.B. Vahovskii, On the characteristic numbers of incidence matr ices for non-singular graphs, Sibirsk. Mat. Zh. 6 (1965), 44-49 (in Russian)

    work page 1965

  16. [16]

    Yan, Enumeration of spanning trees of middle graphs, J

    W.G. Yan, Enumeration of spanning trees of middle graphs, J. Applied Math. and Comput. 307 (2017), 239-243

    work page 2017

  17. [17]

    Yan, On the number of spanning trees of some irregular line g raphs, J

    W.G. Yan, On the number of spanning trees of some irregular line g raphs, J. Combin. Theory Ser. A 120 (2013), 1642-1648

    work page 2013

  18. [18]

    Zykov, On some properties of linear complexes,(in Russian) Mat

    A.A. Zykov, On some properties of linear complexes,(in Russian) Mat. Sbornik N.S. 24 (1949), 163-188 (in Russian). 26

    work page 1949