In one of my algorithm courses, there is this:

A subset $S$ of vertices in a directed graph $G$ is strongly connected if for each pair of distinct vertices ($v_i$, $v_j$) in $S$, $v_i$ is connected to $v_j$ and $v_j$ is connected to $v_i$.

And then the following example graph is given for this proposition:

enter image description here

Maybe i do not understand what that phrase means. What i think it means is this: A node, say $E$ can be a member of an ordered pair $(v_i, v_j)$ only once, ie. if $(E, A)$, then $\lnot (E, [someOtherNode]) $. But we clearly see here, that we have $(E,A)$ and $(E,D)$.

How should i correctly interpret this phrase. What does it mean exactly? Thanks.

  • 2
    $\begingroup$ distinct, I believe, refers not the the pairs but the vertices in the pair. So this condition would not require a vertex to be connected to itself. $\endgroup$ May 12, 2017 at 16:14
  • $\begingroup$ So there can be $(v_1, v_2)$ and $(v_1, v_3)$ and $(v_4, v_1)$, but not $(v_2, v_1)$ because both $v_2$ and $v_1$ have been used already in a pair? That's what i can make of it. $\endgroup$
    – KeyC0de
    May 12, 2017 at 16:20
  • 4
    $\begingroup$ No. The definition doesn't require that the pairs be distinct. In the phrase “pair of distinct vertices“, notice that the adjective “distinct” modifies “vertices”. Jose has it right. $\endgroup$ May 12, 2017 at 16:32
  • $\begingroup$ By the way, I don't think this is a soft question. It's a good question! $\endgroup$ May 12, 2017 at 16:33
  • 1
    $\begingroup$ Maybe I should write an answer then. $\endgroup$ May 12, 2017 at 16:43

3 Answers 3


Also, "connected" does not mean by a directed edge, but by a directed path.

  • $\begingroup$ Good answer but I'd omit the "Also." It seems to me that the meaning of "connected" is the main thing the OP is confused about here. $\endgroup$
    – bof
    May 13, 2017 at 4:31
  • $\begingroup$ @bof, the reason I wrote "also", is that I am not answering the question being asked, as it was in its original form. $\endgroup$
    – vadim123
    May 13, 2017 at 15:26

I think "for each pair of distinct vertices $(v_i, v_j)$ in $S \times S$" means

"for each $(v_i, v_j) \in S \times S$, $v_i \neq v_j$."

  • $\begingroup$ I think here $v_i \neq v_j$ and $i \neq j$ are requirements that lead to same sets. In other words $i \neq j$ is redundant. $\endgroup$
    – KeyC0de
    May 12, 2017 at 16:29
  • $\begingroup$ @RestlessC0bra, thank you for pointing that out. I have removed the redundant condition. $\endgroup$ May 12, 2017 at 16:33
  • 13
    $\begingroup$ Actually, the indices $i,j$ themselves are superfluous. I'd prefer to see this written as "For each $(v,w)\in S\times S$ with $v\ne w$, we have ..." $\endgroup$ May 12, 2017 at 16:58

From your subset $S$ of vertices you can construct a set of pairs $P$, where $(v,w) \in P$ if there is a directed path from $v$ to $w$ (not necessarily confined to $S$). The set is strongly connected if $$ \forall v,w\in S, ( v\neq w \Rightarrow (v,w) \in P \wedge (w,v) \in P) $$ Let $S=G$ in the example graph. Notice that $(A,B)$, $(B,C)$, $(C,D)$, $(D,E)$, $(E,A)$ are all in $P$. So by transitivity, every pair of distinct vertices is in $P$.

The word distinct in the definition rules out the requirement that $(v,v) \in P$. However, it seems that $(v,w) \in P \wedge (w,v) \in P$ would imply that $(v,v)\in P$ anyway.

I'm not sure what you mean by “valid” pair. Any pair may be in $P$; the condition is only that certain pairs must be in $P$.


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.