# Transitive Graph

let R Relation: (u,v) in R iff there is a path between u and v (u and v are graph vertices)

I want to prove that Relation R is transitive, now i've seen than you cant just concatenate Pu->v to Pv->w and you have to cut those pathes at their meeting and only then concatenate.

my question is, why is that?

Thanks.

-
Do you know what "path" means? – Chris Eagle Sep 26 '12 at 14:28
yeah, it meens that there is a sequence of vertices such that from each of its vertices there is an edge to the next vertex in the sequence. – Some1Pr0 Sep 26 '12 at 14:33
A path is a trail in which all vertices (except perhaps the first and last ones) are distinct. – Lrrr Sep 26 '12 at 14:36
@Some1Pr0 vertices must be distinct! – Lrrr Sep 26 '12 at 14:37
why? there is simple path which is a distincted path – Some1Pr0 Sep 26 '12 at 14:53

For paths in general (allowing repetition) then concatenation of the path is perfectly fine. Given paths $$P_{uv} = (u, u_1, \cdots , u_k, v)$$ $$P_{vw} = (v, v_1 , \cdots, v_\ell, w)$$ the concatenated path $$P_{uvw}=(u, u_1, \cdots, u_k, v, v_1, \cdots, v_{\ell}, w)$$ forms the necessary path without problems.
If you want the equivalence relation formed based on simple paths, then you must not only concatenate the paths, but remove any repetitions. Suppose that $v_i$ is the first vertex encountered in the concatenated path which will be repeated at some point. Then there is a sub-path (cycle) from $v_i$ to $v_i$ in $P_{uvw}$ $$P_{uvw} = (u, \cdots ,v_{i-1}, \underbrace{v_i, \cdots, v_i}_\text{cycle}, v_{i+1}\cdots w)$$ then if we contract the cycle, we have a simplified path $$P^\prime_{uvw} = (u, \cdots, v_{i-1}, v_i, v_{i+1} \cdots w)$$ in which the mutliplicity of $v_i$ is reduced by $1$. We can continue this procedure and we can be ensured that this algorithm will eventually terminate since the path is finite. Therefore will will eventually obtain a simple path after the necessary cycle contractions.