# Is connection relation of graph an Equivalence relation?

While Going through Graph theory by West,I found a point where it is written I got the first point that

If a Graph is connected then it have a $uv$ path.

But have some confusions here -:

A Connection relation in a graph is an equivalence relation because it is

• Reflexive Relation (take Path of length $0$)

• Symmetric Relation (reversible path $\rightarrow$ obviously undirected one)

• Transitive Relation-:reason given is

If a Graph has a $uv$ path and also $vw$ path then it will also contain $uw$ path

My Doubt starts here-:

If a Graph contains a $uv$ path and also $vw$ path ,then what is the gurantee that $uv$ path and $vw$ path have NO common Vertex .It Both the path wil have a single common vertex ,it wil no longer a path.

Take the path $uv$, and denote it by $u = u_1, u_2, ..., u_n = v$. Next, take the path $vw$, and denote it by $v = v_1 , v_2, ... , v_m = w$. We will now take two cases:

Case 1: $u_i \neq v_j, 1 \leq i \leq n, 1 \leq j \leq m$. All vertices in both paths are distinct, so we simply take the path $u_1, u_2,...,u_n,v_2, ...v_m$, and are done.

Case 2: $\exists u_i, v_j$ such that $u_i = v_j$. Truncate the length of the first path to be from $u_1$ to $u_i$, and make the second path go from $v_{j+1}$ to $v_m$. Repeat this process until both paths are distinct. Finally, take the path given by $u_1,...,u_i, v_{j+1},...,v_m$.

Hope this helps!

Show that "There exists a path $uv$" is equivalent to "There exists a walk from $u$ to $v$". To do so, you could show that the shortest of possibly several existing walks $u$ to $v$ is in fact a path: The latter follows because any walk $u\ldots w\ldots w\ldots v$ allows a shorter walk $u\ldots w\ldots v$.

Let's say there is a path between $u$ and $v$ if there exists $u_1, \ldots, u_n$ not necessarily distinct s.t. $u_i$ and $u_{i+1}$ are adjacent, $u_1=u$ and $u_n=v$. This path is said simple if $u_1, \ldots, u_n$ are pairwise distinct (except maybe $u_1$ and $u_n$).

Then we can show that the relation "$u$ and $v$ are connected by a simple path" is a transitive relation. If you show that there exists a path between $u$ and $v$, then you can choose one of minimal length. If it is not simple, then we can delete the part between the two same nodes, thus getting a smaller path, contradiction.

• This is not the definition of a path. In a path, all vertices except the first and last must be distinct. – cool.coolcoolcool Dec 27 '16 at 19:11
• @cool.coolcoolcool: There are several definitions... It doesn't matter as long as I recall my conventions. – md5 Dec 27 '16 at 19:43
• No, because if you use a different definition from the OP you will have a different result/proof. – cool.coolcoolcool Dec 27 '16 at 22:41