The existence of a source and sink
Task number: 4457
Let \(G\) be an acyclic oriented graph (note that this is not the same as a tree: we mean a graph without oriented cycles). Prove that in \(G\) there exist vertices \(s\) (source) and \(t\) (sink) such that \({\rm deg}^{\rm in}(s)={\rm deg}^{\rm out}(t)=0\).
Hint
Consider the longest path.Solution
The initial vertex \(s\) of the longest oriented path must be a source: if it was not, there is an edge \((x,s)\) from some vertex \(x\). If \(x\) lies on the path, there is a cycle in the graph; if it does not lie on the path, the path can be extended by the edge \((x,s)\) so that it was not the longest.
We use an analogous argument to prove that the last vertex of the path is the sink.
