We investigate a process of joining $k$ random spanning trees on a fixed clique $K_n$. The joined trees may not be disjoint and multiple edges are replaced by one simple edge. This process produces a simple graph $G$ on $n$~vertices with an edge set, which is a union of edge sets of the joined trees. We study a random variable $S_{k}$ of the number of edges in the generated graph $G$. The exact formula is derived for the expected value of the random variable $S_{k}$. In addition, an upper bound on the concentration coefficient of the random variable $S_{k}$ is provided. We use results of our analysis to design an algorithm to generate $k$-edge connected graphs for arbitrarily large values of $k \geq 2$. The designed algorithm solves a particular case of the Survivable Network Design Problem, where the cost of each edge is $c_{e} = 1$ and the connectivity requirement for each pair of vertices $u, v \in V(G)$ is $k$.The proposed algorithm is within a factor strictly less than $2$ of the optimal value (i.e., the number of edges in the generated graph) and its running time is $O(kn\log{n})$.

翻译：我们研究了在固定团$K_n$上连接$k$棵随机生成树的过程。所连接的树可能不互斥，多重边将被替换为单一边。该过程产生一个具有$n$个顶点的简单图$G$，其边集是所连接树的边集的并集。我们研究了生成图$G$中边数的随机变量$S_{k}$。推导了随机变量$S_{k}$期望值的精确公式。此外，提供了随机变量$S_{k}$集中系数的一个上界。我们利用分析结果设计了一种算法，用于生成任意大$k \geq 2$值下的$k$边连通图。该算法解决了可生存网络设计问题的一个特例，其中每条边的成本为$c_{e} = 1$，且每对顶点$u, v \in V(G)$的连通性要求为$k$。所提出的算法在最优值（即生成图中的边数）的严格小于$2$的因子范围内，其运行时间为$O(kn\log{n})$。