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.

Difficulty level: Easy task (using definitions and simple reasoning)
Reasoning task
Proving or derivation task
Cs translation
Send comment on task by email