





















The number of spanning trees of a graph $G$, denoted $τ(G)$, is a well studied graph parameter with numerous connections to other areas of mathematics. In a recent remarkable paper, answering a question of Sedláček from 1969, Chan, Kontorovich and Pak showed that $τ(G)$ takes at least $1.1103^n$ different values across simple (and planar) $n$-vertex graphs $G$, for large enough $n$. We give a very short, purely combinatorial proof that at least $1.55^n$ values are attained. We also prove that exponential growth can be achieved with regular graphs, determining the growth rate in another problem first raised by Sedláček in the late 1960's. We further show that the following modular dual version of the result holds. For any integer $N$ and any $u < N$ there exists a planar graph on $O(\log N)$ vertices whose number of spanning trees is $u$ modulo $N$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。