# Proof: every consistent heuristic is also admissible

Proof: Let $h\left(x\right)$ be any consistent heuristic, and let $c\left(x,y\right)$ be the corresponding step cost of moving from the state x to another state y. Then $h\left(x\right)\le c\left(x,y\right)+h\left(y\right)$ by the definition of consistency. To show that h is admissible, we must show that $h\left(x\right)\le p\left(x\right)$ where p is the path cost of x.

Suppose there is no path from x to the goal state. In this case, $p\left(x\right)$ is infinite, and satisfies that $h\left(x\right)\le p\left(x\right)$ for any finite $h\left(x\right)$.

Now suppose that there is some path form x to a goal state g. Let us call intermediate nodes of a shortest path ${w}_{1},{w}_{2},\dots {w}_{n}$. So the shortest path from x to g is expressed as $\left(x,{w}_{1},{w}_{2},\dots {w}_{n},g\right)$.

Now consider $h\left({w}_{n}\right)$. Since h is consistent, $h\left({w}_{n}\right)\le c\left({w}_{n},g\right)+h\left(g\right)=c\left({w}_{n},g\right)$ since $h\left(g\right)=0$. Similarly, $h\left({w}_{n-1}\right)\le c\left({w}_{n-1},{w}_{n}\right)+h\left({w}_{n}\right)\le c\left({w}_{n-1},{w}_{n}\right)+c\left({w}_{n}\right)$. By induction on n, we obtain $h\left({w}_{k}\right)\le c\left({w}_{k},{w}_{k+1}\right)+\cdots +c\left({w}_{n-1},{w}_{n}\right)+c\left({w}_{n},g\right)$ for any k between 1 and n-1. But because $\left(x,{w}_{1},{w}_{2},\dots {w}_{n},g\right)$ is a shortest path, $p\left({w}_{k}\right)=c\left({w}_{k},{w}_{k+1}\right)+\cdots +c\left({w}_{n-1},{w}_{n}\right)+c\left({w}_{n},g\right)$ so that $h\left({w}_{k}\right)\le p\left({w}_{k}\right)$ as desired.

Q.E.D.