This is a questions regarding how to follow the given solution. Sorry for my improving English skill and asking this stupid question. Really appreciated any help. as learned in lecture:
First layer: all nodes that are sources
Next layer: all nodes that are now sources(once we remove previous layer and its ongoing edges)
Number of layers is the same as the number of vertices in the longest path in G?
Given solution:
Proof. Observe that any two vertices of DAG G cannot be in the same layer. Now suppose by contradiction that the number of layers in G is NOT THE SAME as the number of vertices in the longest path of G. Let p be the number of vertices of the longest path and l be the number of layers of G. By our assumption p 6= l so we have two cases
Case 1: l < p. That is, number of layers less than number of vertices in longest path. By the pigeonhole principle, there will be at least two vertecies on the longest path that are also in the same layer. This is impossible, hence a contradiction.
Case 2: l > p. That is, number of layers greater than number of vertecies in longest path. It is impossible to have more layers than p, the number of vertecies in the longest path. Hence, we also have a contradiction. In both of our cases we have contradictions. Hence our assumption that the number of layers in G is not the same as the number of vertecies in the longest path of G must be wrong. This completes the proof.
The sentence in bold is the part, I don't understand it. I can't observe that"Observe that any two vertices of DAG G cannot be in the same layer". because I think there could be more than one vertices in a layer. For example: a directed graph of tree. can't we consider all the immediate sub-tree of root as one layer? Please help, thank you.