Tree-packings – collections of spanning trees of a graph – are a fundamental tool in the study of minimum cut and related graph parameters. They have played a central role in the design of algorithms across static, dynamic, and distributed settings. In this paper, we study both tree-packings themselves and their structural connections to min-cut and arboricity. Our results lead to faster dynamic algorithms for both problems. For dynamic min-cut, [Thorup, Comb. 2007] used tree-packings to obtain his dynamic min-cut algorithm with \(\tilde{O}(\lambda ^{14.5}\sqrt{n})\) worst-case update time. We reexamine this relationship, showing that we need to maintain fewer trees for such a result; we show that we only need to pack \(\Theta (\lambda ^3 \log m)\) greedy trees to guarantee either a 1-respecting cut or a trivial cut in some contracted graph. Based on this structural result, we then provide a deterministic algorithm for fully dynamic exact min-cut that has \(\tilde{O}(\lambda ^{5.5}\sqrt{n})\) worst-case update time, for graphs with min-cut value at most \(\lambda \) . In particular, this also yields an algorithm for fully dynamic exact min-cut with \(\tilde{O}(m^{1-1/12})\) amortized update time, improving upon \(\tilde{O}(m^{1-1/31})\) [Goranci et al., SODA 2023]. We also give the first fully dynamic algorithm that maintains a \((1+\varepsilon )\) -approximation of the fractional arboricity. Our algorithm is deterministic and has \(O(\alpha \log ^6m/\varepsilon ^4)\) amortized update time, for graphs with arboricity at most \(\alpha \) . We extend these results to a Monte Carlo algorithm with \(O(\operatorname {poly}(\log m,\varepsilon ^{-1}))\) amortized update time against an adaptive adversary. Our algorithms work on multi-graphs as well. Our structural results on tree-packing also include a lower bound for greedy tree-packing, which – to the best of our knowledge – is the first progress on this topic since [Thorup, Comb. 2007].
