Suppose we are given a directed acyclic graph $G$, and each node is assigned a label with two real numbers like in the following example. We are given a set of source vertices and a set of sink vertices. We construct a new graph where all source vertices are replaced by one vertex, all vertices reachable from the source vertices by another vertex and so forth. We then assign labels to these new vertices as follows: for the first label we take the maximum value of all the labels in that reachable set and for the second label we take the minimum value of all the lables. Like for $L_1$ we take the maximum of $(40,10)$ and the minimum of the second label that is minimum of $(8, 6)$ and thus the label of the new graph is $(40, 6)$.
I have written this formally as follows:
Let $G=(V,E)$ be a directed acyclic graph. Consider $source \subset V$ to be source vertices which have no inward edges into them and $sink \subset V$ to be sink vertices from which no outward edges are present. Consider $L_k = \{v | distance(source, v) = k\}$ , ie, $L_k$ is the set of vertices which are at a distance $k$ from the source vertices. Each vertex is labeled with two real numbers defined by the functions $a$ and $b$ $a : v \rightarrow \mathbb{R}$ and $b : v \rightarrow \mathbb{R}$, $\forall v \in V$.
Consider a new graph $G'=(V',E')$ where $|V'| = k$. and each vertex in this graph corresponds to a set $L_i$ of the graph $G$, ie, there is a bijective function $f:L_i \rightarrow v_i$, $\forall i, 1\leq i \leq k $. The edge set $E'$ of this graph is defined as $\{(v_i, v_{i+1}, \forall i, 1 \leq i \leq k-1\}$. Thus, this new graph is a path graph. Similar to the original graph, each vertex in this graph is labeled with two real numbers defined by the functions $a' : v' \rightarrow \mathbb{R}$ and $b' : v' \rightarrow \mathbb{R}$ where $a'(v_i') = max\{a(v), \forall v \in L_i\}$ and $b'(v_i') = min\{b(v), \forall v \in L_i\}$, $\forall 1 \leq i \leq k$.
Is this formalism correct? Now we need to show that if there is a particular vertex in the new graph such that its first label value is $\ge x$ then there is a path in the original graph also where there is a vertex whose first label is $\ge x$. Like for instance in the example above, if $x$ is say $50$, then the third vertex in the new graph has the first label as $60 \ge 50$. There is a path is the original graph where the first label is also $60 \ge 50$. If this is not true provide a counterexample. I have again written this formally below.
Prove that if in the path graph $G'$ there is a vertex $v'$ such that $a'(v') \geq x$ then there is a path $v \in G$ from source to sink such there is a vertex $v$ where $a(v) \geq x$ and if in the path graph $G'$ there is a vertex $v'$ such that $b'(v') \leq x$ then there is a path $v \in G$ from source to sink such there is a vertex $v$ where $b(v) \leq x$ or provide a counterexample. Is this formal definition correct?
Attempt : I tried to find a counterexample but could not find any. So for the proof attempt I tried arguing on the basis of the paths. For the first case, if in the path graph $G'$ there is a vertex $v'$ such that $a'(v') \geq x$, then let us label this path as $v_0, v_1, v_2…v_k$ and the first vertex where the label $a'$ of the vertex $\ge x$ be $v_n$. Assume for the purpose of contradiction that such a path does not exist in the original graph $G$. This means that the first label of all paths in the original graph $G \lt x$. When building the new graph $G'$ we assigned the label of the vertex as the maximum value of all the labels in $L_i$. As a result of this construction, we have built the new graph $G'$ and obtained a vertex where its first label is $\geq$x. For this vertex to be present in the new graph $G'$ it would have to be present in the original graph $G$ as well otherwise it could not be present in the new graph $G'$. This contradicts our claim that that such a path does not exist in the original graph $G$.
Is this proof correct or am I missing something or am I on the wrong track here?
Best Answer
It seems for me your arguments are right, but you overcomplicated a simple situation. If $a′(v′)\ge x$ (resp. $b′(v′)\le x$) then there exists a vertex $v$ (which lies in a path from the source to sink) of $G$ such that $a(v)=a’(v’) \ge x $ (resp. $b(v)=b′(v′)\le x$). $\square$