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.

I am stuck here ,please help me out..!!!


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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.