I've been trying to study some graph algorithms and, as part of it, prove a bunch of graph theorems in order to practice my ability to do theoretical work with graphs.
Specifically, I've been trying to prove that given a directed graph $G$, the minimal (in terms of vertex count) non-empty subset of vertices with no outgoing edges (i.e, the minimal non-empty set $M$ that holds the property that for all $v\in M$ and $u\in G$, if there is an edge $(v,u)$ then $u\in M$) is one of the two:
- The minimal (again: in terms of vertex count) strongly connected component with no outgoing edges, or
- If there is no such SCC with an out-degree of zero: that set is the entire graph (or its set of vertices, rather).
Whichever direction I try taking, I end up feeling stuck very fast. For one example of a failed attempt: I've been trying to show #2; that is to say, analyze the case in which there are no SCC with an out-deg of 0 in graph $G$. For this case I assumed (intending to prove by contradiction) that there exists an $M$ which is a strict subset of $G$'s set of vertices and it holds the property described above. If $M$ is strongly connected then it is an SCC with no outgoing edges due to having the property, which is a contradiction to the assumption of this case, so $M$ is not strongly connected. Hence, there exist vertices $v,u\in M$ such that there is no path from $v$ to $u$. And... that's about as far as I could get. I'm not sure how to even begin proceeding from here. I want to show that $M$ has an outgoing edge somehow, but there appear to be so many end cases that I struggle with finding something common to bind them all together.
Would greatly appreciate a hint or outlines for how to proceed (or corrections if I've made any false claims) to help me get a grasp of the process here.