A central challenge in network design is ensuring resilience: how can we guarantee multiple, independent, communication pathways between nodes, even when some connections fail in a network? In 1989, Zehavi and Itai formulated a graph-theoretic conjecture that captures the essence of this problem. They proposed that any \(k\)-vertex-connected graph contains \(k\) independent spanning trees rooted at any given root \(r\), which means that for every vertex \(v\) in the graph, the unique \(r-v\) paths within these \(k\) spanning trees are entirely disjoint, apart from their endpoints \(r\) and \(v\). Despite decades of effort, this conjecture has only been proven for \(k \le 4\) and for specific graph families using their underlying topological structure, leaving the general case as an open problem in graph theory with substantial consequences in the field of distributed algorithms.

A graph $G$ is Ramsey for a graph $H$ if every 2-coloring of the edges of $G$ contains a monochromatic copy of $H$. We consider the following question: if $H$ has bounded treewidth, is there a “sparse” graph $G$ that is Ramsey for $H$? Two notions of sparsity are considered. Firstly, we show that if the maximum degree and treewidth of $H$ are bounded, then there is a graph $G$ with $O(|V(H)|)$ edges that is Ramsey for $H$. This was previously only known for the smaller class of graphs $H$ with bounded bandwidth. On the other hand, we prove that in general the treewidth of a graph $G$ that is Ramsey for $H$ cannot be bounded in terms of the treewidth of $H$ alone. In fact, the latter statement is true even if the treewidth is replaced by the degeneracy and $H$ is a tree.

Aharoni and Berger conjectured that in any bipartite multigraph that is properly edge-colored by $n$ colors with at least $n + 1$ edges of each color there must be a matching that uses each color exactly once. In this paper we consider the same question without the bipartiteness assumption. We show that in any multigraph with edge multiplicities $o(n)$ that is properly edge-colored by $n$ colors with at least $n + o(n)$ edges of each color there must be a matching of size $n-O(1)$ that uses each color at most once.