# Optimum first stage solution of two stage stochastic shortest path induces tree

I struggle with the proof of Lemma 1 in the Paper "Hedging Uncertainty: Approximation Algorithms for Stochastic Optimization Problems" by Ravi and Sinha and hope this is the right community to ask for help.

Problem setting: There is a graph $$G(V,E)$$ with edge costs $$c_e$$ and a source vertex $$s \in V$$. Now there are $$m$$ scenarios for the second stage, with scenario $$k$$ specified by a destination vertex $$t_k \in V$$, a multiplicative cost scale factor $$f_k$$ and a probability $$p_k$$ with which the scenario occurs. If we chose a set of edges $$E' \subset E$$ in the first stage they have the cost $$\sum_{e \in E'}c_e$$. Then in the second stage a scenario $$k$$ occurs and we have to calculate a second stage solution for the shortest path $$P_k$$ between $$s$$ and $$t_k$$. We assume that the edges of the first stage ($$E'$$) have now cost zero while the remaining edge costs increase by $$f_k$$. This results in the following total first and second stage costs: $$\sum_{e \in E'}c_e + f_k \sum_{e \in P_k \setminus E'}c_e$$ The objective is to find the edge-subset $$E'$$ that minimizes the total costs.

Lemma: Now they say that there exists an optimum solution where the set $$E'$$ induces a tree containing the source $$s$$. I copy their proof here for simplicity: My problems and thoughts:

• At first I had problems with the first sum $$\sum_{P_k \ni e}p_kf_k \ge 1$$, but now I think it means, that, in optimum, for any first stage edge the expected cost increase for all scenarios in which the edge is part of a shortest path must not be smaller than 1. Because if the sum was smaller than one, I would save cost if I get the edge in the second stage, which contradicts the optimum assumption. Is this correct?
• Now i don't get, how this statement implies $$\sum_{k \in K'} f_k \ge 1$$. I get that for every scenario in $$K'$$ there is at least one edge used for $$P_k$$ for which the above statement is true, but I don't see the logical transition from the edges to the sum of cost factors. I see that this sum is already bigger than 1 if there is only one scenario with $$f_k > 1$$ but this doesn't help me to grasp the implification.