Colour ratio in Prim's ranking of bipartite graphs

Félix Kahane, Minmin Wang

We consider a complete bipartite graph of size $n$ endowed with i.i.d. uniform edge weights and run Prim's Algorithm to obtain a ranking of its vertices. Let ${\rho }_k^{(n)}$ be the pro…