1
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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! $\endgroup$
    – Shay
    Dec 4, 2022 at 20:29
  • $\begingroup$ 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. :-) ) $\endgroup$
    – Shay
    Dec 4, 2022 at 20:31
  • $\begingroup$ You are welcome! $\endgroup$
    – John L.
    Dec 4, 2022 at 20:54
  • 1
    $\begingroup$ I have updated my answer accordingly. $\endgroup$
    – John L.
    Dec 4, 2022 at 20:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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