Consider a graph $G=(V,E)$ and an MST of $G$. I am wondering how many edges I need to store, to make the MST tolerant to edge failures.
If there is only one edge failure, I require at most $n-1$ edges in addition to the edges that are part of the MST. This is because for every edge on the tree, I can simply compute the best alternative edge.
But how does this change if I allow for more than one edge failure? Does linear memory ($O(n)$) still suffice for two edge failures? If yes, after how many failures will linear memory not suffice any longer?