BEST 定理
记 \(G\) 是一个有向欧拉图，\(t^{in}(G,k)\) 表示图 \(G\) 以 \(k\) 点为根的内向生成树个数，\(\varepsilon(G)\) 表示图 \(G\) 的欧拉回路数，\(\deg(v)\) 表示点 \(v\) 的入度（等于出度），有：
\[\varepsilon(G)=t^{in}(G,k)\prod_{v\in V}(\deg(v)-1)!
\]
其中 \(k\) 可以为任意顶点。注意这里欧拉回路是循环同构的。
\(t^{in}(G,k)\) 使用矩阵树定理求即可。
证明
我们只需将以 \(k\) 为起点的欧拉回路与以 \(k\) 为根的内向生成树联系起来即可。首先我们将公式写作：
\[\varepsilon(G)\deg(k)=t^{in}(G,k)\deg(k)!\prod_{v\in V\setminus\{k\}}(\deg(v)-1)!
\]
该公式的构造意为：
- 内向生成树的树边就是子节点在欧拉回路上最后一次走的出边。
- 根节点的所有出边任意排列方案数 \(\deg(k)!\)。
- 非根节点的所有非树出边任意排列方案数 \(\prod_{v\in V\setminus\{k\}}(\deg(v)-1)!\)。
- 对于同一个欧拉回路，其中 \(k\) 节点出现了 \(\deg(k)\) 次（终点即为起点不另算），每一个位置都会被算一遍，故而会算重 \(\deg(k)\) 次。
只需证明这样构造出了一个双射即可。
我们先证明每条欧拉回路都唯一对应上述生成树和出边顺序。
唯一对应出边顺序是显然的，只需证明非根节点的最后一条出边能形成一个内向生成树。若不能则必然成不包含根节点的环且终止在非根节点上，欧拉回路必然在起点中止，矛盾，得证。
接下来我们证明每组生成树和出边顺序都唯一对应一条欧拉回路。
首先我们直接按照给定的出边顺序模拟，由于是欧拉图入度等于出度所以最后必然能走回到根节点，只需证明每条边都会被走过即可。我们归纳法证明：首先这条边不可能是根节点的出边；其次，一个点有出边没被走过，当且仅当其有入边没被走过，并且其树边必然没被走过，故而其树上父节点也有出边剩余，最后会推到根节点，矛盾，不成立。
证毕。