How to inductively prove a graph property? I'm stuck on Part 1, I can't find it inductively. The distance from $$[k, k + 1]$$ is going to be a non-zero positive value with a vertex. Therefore, there is going to be a positive edge weight from $$w(uv)$$ that goes from $$[k, k + 1].$$ Therefore, there exists a v on the set of V such at $$A[u, k + 1] = A[v, k] + w(uv).$$
The Problem
Given an undirected graph $G = (V, E)$ with positive edge weights $w(e)$ for each edge $e \in E$, we want
to find a dynamic programming algorithm to compute the longest path in $G$ from a given source $s$
that contains at most $n$ edges.
To do this first define $A[v, k]$ as the weight for the longest path from node $s$ to node $v$ of at most
$k$ edges.

*

*First we need to prove an optimal sub-structure by induction. Show
that if $A[v, k]$ is the weight of the longest path, then for all $u
  \in V$, there exists a $v \in V$ such that $A[u, k + 1] = A[v, k] + w(uv)$.

*Describe a dynamic programming algorithm that finds the optimal
length using part 1.  Specifically: describe (1) the OPT recurrence
(2) the running time of the iterative solution for computing the OPT
table.

 A: We would like to know what is the maximum weight path of length at MOST $k+1$ from source $s$ to vertex $u$. Obviously such a path must exist (assuming connected).
Now, assume such a path EXIST (we know nothing more!!), and we can describe the path by the sequence of vertices it goes through, that is, path $p_1:=\{s,v_0,...,v\}$. Note that we don't actually know the sequence of vertices, just that if such a path exist then it must have a sequence of vertices that describe the path.
Now, consider the last vertex on said sequence before $v$. Call it $u$. Of course, the path (up to $u$) can have a length of AT MOST $k$. Note that from the sequence, edge($u$,$v$) is in the maximum weight path to $v$ (that has length at most $k+1$).
I'm going to show why the weight of the path $p_1$ minus the edge($u$,$v$) is also the entry of $A[u,k]$. That is, the path $p_1$ minus the edge($u$,$v$) (let's call this $p_2$) is the maximum weight path from the source $s$ to vertex $u$ of length at most $k$.
Suppose $p_2$ is not the maximum weight path from $s$ to $u$. That is, there exist path $p_3$ that has a larger weight, and it has at most $k$ edges. But then $p_3$ added with edge($u$,$v$) has larger weight than $p_1$ (our maximum weight path from $s$ to $v$ with length at most k+1). Thus we have a contradiction.
To recap: we have proved that the weight of the path $p_2$ must be the entry of $A[u,k]$. But what is the weight of path $p_2$? Remember that we get $p_2$ by deleting edge($u$,$v$) from path $p_1$. Of course, it means that the weight of $p_2$ is weight of $p_1$ minus the weight of edge($u$,$v$).
$$
A[v,k+1] - w(uv) = A[u,k], \implies A[v,k+1]  = A[u,k] + w(uv)
$$
