# 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.

1. 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)$$.
2. 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.
• Do u understand what the entries of the matrix mean? Commented Nov 4, 2021 at 17:55
• Matrix, I believe it's a graph and not a matrix? Commented Nov 4, 2021 at 17:56
• $A$ is a matrix, $G$ is a graph. Commented Nov 4, 2021 at 18:13

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)$$

• Feel free to ask further questions Commented Nov 4, 2021 at 18:25
• Well but we have to be careful here though. What if $p_3$ contains the vertex $v$? Your argument carries through if we replace 'path', where repeating vertices are not allowed, with 'walk', where repeating vertices are allowed.
– Mike
Commented Nov 4, 2021 at 19:42
• Meanwhile, unless P=NP, there is no algorithm to find the longest path with at most $k$ edges in a weighted graph starting from a vertex $s$; if so, then there would be an algorithm that would find a Hamiltonian path starting from a vertex $s$. Indeed, ask for the longest path starting from $s$ that has at most $|V(G)|$ vertices, where the weight of each edge in $G$ is exactly $1$.
– Mike
Commented Nov 4, 2021 at 19:47
• @Mike I.. considered a directed simple graph. I will try to correct the answer Commented Nov 4, 2021 at 20:17
• @Mike is the question correct? The first part is the same as asking "show that for any vertex $v$, that has a maximum weight path $p_v$ of length at most $k+1$, at least one of it's neighbours $u$ must have the same path $p_v$ minus one edge($u$,$v$) as it's maximum weight path of length at most $k$". If that re-wording is correct, I can draw a graph where that statement is not true. Commented Nov 4, 2021 at 20:35