How to prove that there is always a path in a DAG that goes through all vertices in a chain?

163 Views Asked by At

Consider the following claim.

Let S be a set of vertices in a DAG (directed acyclic graph), G. There is a path in G that goes through all vertices in S IFF S is a chain.

I can see the truth of the claim in the forward direction but not in the backward direction. Namely, I can't prove

If S is a chain, then there is a path in G that goes through all vertices in S.

The definitions I used for paths and chains are the ones found in Mathematics for Computer Science(path in page 371 [page 379 in the pdf] and chain, Definition 10.5.5., in page 381 [page 389 in the pdf].

Additionally, if the claim is true, is it still true if G is a directed graph instead of a DAG.

1

There are 1 best solutions below

0
On

Yes, i was oversimplifying in the comments. Sorry

Consider a set $S=\{s_1,s_2,\cdots ,s_k\}$ to be a chain then all of them are comparable(by definition), meaning that they are of the form $s_1\leq \cdots \leq s_k$ where $a\leq b$ means that there is a path from $a$ to $b$ in the DAG. Then, we have a path from $s_1$ to $s_2,$ another path from $s_2$ to $s_3$ and so on. Call the path from $s_i$ to $s_{i+1}$ $p_i,$ and then concatenate the paths as $p_1p_2\cdots p_{k-1},$ this will be a path from $s_1$ to $s_k.$