On the intersection of pairs of trees
We consider the number of common edges in two independent random spanning trees of a graph $G$. For complete graphs $K_n$, we give a new proof of the fact, originally obtained by Moon, that the distribution converges to a Poisson distribution with expected value $2$. This is applied to show a Poisson limit law for the number of common edges in two independent random spanning trees of an Erdős--Rényi random graph $G(n,p)$ for constant~$p$, as well as a central limit theorem in the case where $p\to 0$ and $p\geq n^{-2/3+\gep}$. We also use the same method to prove an analogous result for complete multipartite graphs.
Authors
- Miklós Bóna (ORCID: https://orcid.org/0000-0002-8711-7281)
Publication Details
- Journal
- European Journal of Combinatorics
- Published
- 2026-09-09
- DOI
- https://doi.org/10.1016/j.ejc.2026.104437
- Primary Topic
- Graph Labeling and Dimension Problems
- Type
- article
- Field-Weighted Citation Impact
- 0.00