# Uniform Cost Search on Graph Proof

I am trying to prove the following:

For any positive natural n, there exists an undirected graph of n nodes, positive natural edge widths, and nodes s and t such that a uniform-cost search from s examines all the nodes, whereas the optimal path from s to t consists of only a single edge.

-

Here's a proof by induction. However, the case $n=1$ is a special case. Say node $s$ is also node $t$. Otherwise, if this is not allowed, then it cannot be proven.
Now the real base case is $n=2$. This is trivial. The graph that satisfies this case consists of two nodes $s$ and $t$, connected together. Note that the edge from $s$ to $t$ is visited last.
For the inductive case, consider that we have the graph of $n$ nodes, and the edge from $s$ to $t$ is visited last. Then we add another node, connect it to $s$ with a cost less than the cost from $s$ to $t$. Thus it will be visited before the edge between $s$ and $t$, so we have preserved that the edge from $s$ to $t$ will be visited last. Further, we have now shown an example for $n+1$, therefore this proves the inductive case. QED
Is induction really necessary? Maybe I don't understand the problem, but it seems to me all you need is an edge from $s$ to $t$, and edges from $s$ to each $v_i$, $3\le i\le n$, and each $v_i$ to $t$, such that each $sv_i$ costs less than $st$ but each $v_it$ costs more than $st$ minus $sv_i$. – Gerry Myerson May 1 '11 at 4:23