# Proof Branch and Bound always finds optimal path in a graph?

I've been studying Branch and Bound's graph algorithm and I hear it always finds the optimal path because it uses previously found solutions to find others, but I haven't been able to find a proof on why it finds the optimal path(In fact most sites kind of do a bad job generalizing the algorithm itself). I was wondering what the proof is that this algorithm always find the optimal path in the case of a graph with 1 or more goal nodes?

• Branch and bound is a paradigm and not a single algorithm. Which algorithm are you specifically referring to? Is it the algorithm that finds the optimal path between two points of a graph? – nbro May 19 '19 at 20:26
• O sorry I'll update the question now. Thanks for letting me know though! I've only seen it in the context of a graph algorithm. – Dylan Y May 19 '19 at 20:38
• Check this question: math.stackexchange.com/q/2915145/168764. Essentially, B&B can degenerate to an exhaustive search, which, in case the graph has a finite number of nodes, should find the optimal solution. However, I don't have a formal proof and I would like to see it too. – nbro May 19 '19 at 20:44
• I feel like a quick proof would be a proof by contradiction maybe? Like assume there's a solution more optimal then the one found by B&B, which means it's cheaper in total cost, but that creates a contradiction because if there is a cheaper path it would have been explored by B&B because B&B would only stop searching after it's pruned everything more expensive or searched everything? – Dylan Y May 19 '19 at 20:56
• That might be a good approach, but this is just an intuition. You might assume that an exhaustive search (on a graph with a finite number of nodes) is able to find the optimal solution and then you just need to worry about the "bound" part, that is, that the pruning of the tree (or search space) doesn't exclude a possible optimal solution. – nbro May 19 '19 at 21:07