K-connectivity reflective, symmetric, transitive

Question

I have to prove the following:

In a directed graph if there are k distinct paths (which don't use the same edges) from vector x to y and also there are k distinct paths(which don't use the same edges) from vector y to x we symbolize it like this: x ≡𝑘 y and we call them k-connected vectors.

I have to prove that this relation is reflective, symmetric, and transitive.

Also, does anything change if the paths use distinct vectors and edge all together?

Answer 1

• Reflexive property:

  If you consider k the number of distinct (not using the same edges) loops containing node x, then for every x, we have some k that holds x ?? x.

• Symmetric property:

  (x ?? y) means:

  (there are k distinct paths from x to y.) and (there are k distinct paths from y to x.)

  (y ?? x) means:

  (there are k distinct paths from y to x.) and (there are k distinct paths from x to y.)

  So because of the symmetry of Logical Conjuction, (x ?? y) implies (y ?? x) and vice versa.

• Transitive property:

  Suppose we have (x ?? y) and (y ?? x)

  the first implies that (there are k distinct paths from x to y; we name them a_1 to a_k in arbitrary order) and (there are k distinct paths from y to x; we name them a'_1 to a'_k).

  the second implies that (there are k distinct paths from y to z; we name them b_1 to b_k in arbitrary order) and (there are k distinct paths from z to y; we name them b'_1 to b'_k).

  we can construct c_1 from concatenating a_1 and b_1 because a_1 ends at y and b_1 starts at y. so c_1 is a path from x to z. this way we can build c_2 to c_k too. for any i and j, c_i and c_j don't have same edges, because their parts (a_i and a_j and b_i and b_j) don't share the same edges. so there are k distinct paths from x to z.

  the same way we can construct c'_1 to c'_k from a'_1 to a'_k and b'_1 to b'_k. so there are k distinct paths from z to x.

  So we can imply that (x ?? z).

The proof holds if paths don't share vectors too. Because that implies, they don't share edges which is an assumption for this proof.