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

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. – Nikos May 12 '17 at 16:29
• @RestlessC0bra, thank you for pointing that out. I have removed the redundant condition. – Arnie Bebita-Dris 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 ..." – Hagen von Eitzen May 12 '17 at 16:58

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. – vadim123 May 13 '17 at 15:26

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$.