I prefer computer typed answer because I could not understand bad hand writing.
ID: 3119401 • Letter: I
Question
I prefer computer typed answer because I could not understand bad hand writing.
Also, if you try to answer only part of question for taking your score, I will report you to Chegg. Please do not take my question for free.
The question is related to 'Graph Theory and Non-Enumerative Combinatorics'
Thank you in advance and I apologize for being aggressive because of many free question takers.
Let G be a simple graph. Let w be a path in G. Prove that the edges of w are (This may look obvious when you can point to a picture; but we ask you to give a rigorous proof!)Explanation / Answer
It would have been of great help had you provided your definition of a 'path'. Nevertheless, in this case, I will understand path as a sequence of adjacent vertices (finite or infinite) without any repeatation of vertices.
Let w = v1 - v2 - v3 - ... - vk - vk+1 - .... be a path i.e. a sequence of adjacent vertices in G. Therefore, (vi , vi+1) is an edge of G for every i > 0 and vi not equal to vj for any distinct i and j.
Let there be a repeated edge in the path w. Therefore, there exist l and m such that (vl , vl+1) = (vm , vm+1) in w.
Since an edge is an unordered pair, we must either have vl = vm or vl = vm+1.
But this contradicts the fact that there is no repeatation of vertices in a path.
Therefore, there can be no repeated edge in a path.