Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

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

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.