In "AI: A Modern Approach", 4th edition, by Russell and Norvig, they give a purported proof that A* is cost-optimal for any admissible heuristic. The given proof seems most certainly wrong. They want to show that all nodes on the optimal path are expanded. Towards a contradiction, they consider a node n on the optimal path that is not expanded, and say that its evaluation f(n) must be strictly greater than the optimal cost C*, for "otherwise, n would have been expanded".
In other words, they claim that a node n with f(n) less or equal than C* will be expanded. That claim is obviously not true in general? Take the heuristic that is identically zero; it is trivially admissible. Now consider a model with initial state A, which can transition to states B, C and D with costs 1, 2 and 3, respectively. Then B, C and D all transition to the goal state E, all with cost 3. The A* algorithm will simply expand B, then E. So it certainly finds an optimal path. Note that states C and D have no chance to be expanded. Nevertheless, they have evaluations 2 and 3, which are both less than 4, the optimal cost. So the claim does not hold.
I would like confirmation of my analysis - is the proof given in the book incomplete?
Just to be clear, I am not saying that A* is not always cost-optimal for any admissible heuristic, although I would love to see a reference (I've found research papers but they are about other notions of optimality, such as number of nodes expanded.) I am just saying that the proof given in the book is wrong.