0
$\begingroup$

The following statement is considered true:

In a DAG, for every vertex $v$, there exists a sink $s$ such that there is a path from $v$ to $s$.

However, my counter example to this is a binary search tree. The leaf nodes in a binary tree do not have a path from themselves to a sink. Hence, am I interpreting this statement incorrectly?

$\endgroup$
3
$\begingroup$

A sink is a vertex with an out degree of zero. The leaf nodes of a binary search tree are the sinks. This is the trivial case of the statement as a path always exists from a node to itself, this path contains no edges, however the statement never said for vertex $v$, the sink $s$ could not be itself. Without this not only is the statment not true, but for every graph it is untrue since all DAGS have at least one sink and that sink could not be paired with another sink since that defeats the nature of a sinc.

$\endgroup$
2
  • $\begingroup$ Oh i see! One had to note that a node can be considered its own sink. That's tricky. So does that mean, in any graph with $n$ number of vertices, there are at least $n$ sinks? $\endgroup$ – Jonathan Dec 8 '16 at 20:48
  • $\begingroup$ @Christian Graph with $n$ vertices, there are at most $n$ sinks. Which is when there are no edges at all. $\endgroup$ – Apiwat Chantawibul Dec 8 '16 at 21:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.