# Proof: every consistent heuristic is also admissible

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

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

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 $$(x,{w}_{1},{w}_{2},\dots {w}_{n},g)$$.

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

Q.E.D.