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

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.

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.

• Thanks a lot :) I wasn't familiar with the concept of a graph's condensation; this seems really cool and useful. Your proof was also very thorough and easy to follow. Much appreciated!
– Shay
Dec 4, 2022 at 20:29
• I also just noticed that I accidentally wrote "in-degree" in places where I meant to have "out-degree" – my bad! Just fixed. (It didn't actually affect the question or your proof because when I actually described the question I just wrote "outgoing edges", fortunately. :-) )
– Shay
Dec 4, 2022 at 20:31
• You are welcome! Dec 4, 2022 at 20:54
• I have updated my answer accordingly. Dec 4, 2022 at 20:54