# Explain phrase "For each pair of distinct elements" in reference to a graph.

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:

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.

• 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. May 12 '17 at 16:14
• 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. May 12 '17 at 16:20
• 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. May 12 '17 at 16:32
• By the way, I don't think this is a soft question. It's a good question! May 12 '17 at 16:33
• Maybe I should write an answer then. May 12 '17 at 16:43

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

• 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.
– bof
May 13 '17 at 4:31
• @bof, the reason I wrote "also", is that I am not answering the question being asked, as it was in its original form. May 13 '17 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$."

• 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. May 12 '17 at 16:29
• @RestlessC0bra, thank you for pointing that out. I have removed the redundant condition. May 12 '17 at 16:33
• 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 ..." May 12 '17 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$.