(Directed) Graphs: Minimal Vertices Subset With No Outgoing Edges

Question

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:

1. The minimal (again: in terms of vertex count) strongly connected component with no outgoing edges, or
2. 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.

Answer 1

There is no wonder you end up feeling stuck. Assume $G$ has at least one vertex. The second case, "there is no such SCC with an out-degree of zero" does not exist.

Recall if each strongly connected component (SCC) of $G$ is contracted to a single vertex, the resulting graph $\mathcal C(G)$, the condensation of G is a directed acyclic graph. Any leaf vertex (i.e., has no outgoing edge) in $\mathcal C(G)$ comes from an SCC of $G$ that has no outgoing edges, i.e., with an out-degree of zero.

---

Let us prove the desired theorem.

Suppose $G$ is a non-empty digraph and $S$ is a non-empty subset of vertices in $G$ that has no outgoing edges. For any vertex $v$ in $S$, let $\text{SCC}_v$ be the strongly connected component of $G$ that contains $v$. ($\text{SCC}_v$ is only defined for $v\in S$)

Since $S$ has no outgoing edges, if vertex $v$ is in $S$ and $(v,u)$ is an edge, $u$ must also be in $S$. Iterating this process, we see that any vertex that is reachable from $v$ by a (directed) path must also in $S$. Well, any vertex is reachable from any vertex in an SCC. Hence, all vertices in $\text{SCC}_v$ must be in $S$. $$S=\cup_{v\in S}\text{SCC}_v$$

There must be an $\text{SCC}_v$ that has no outgoing edges. That is because $\mathcal C(G)$ is acyclic. In particular, the subgraph of $\mathcal C(G)$ consisting of $\text{SCC}_v$'s is acyclic. That subgraph has a leaf vertex, say $\text{SCC}_w$, which means vertices in $\text{SCC}_w$ do not have outgoing edges to vertices in any other $\text{SCC}_v$. Since there is no outgoing edges from vertices in $S$ to vertices outside $S$, vertices in $\text{SCC}_w$ do not have outgoing edges in $G$.

If $S$ is minimal among all no-outgoing-edges subsets of vertices, then $S$ should be the only $\text{SCC}_v$ in it that has no outgoing edges. Then $S$ should be the minimal SCC that has no outgoing edges.