Discrete Maths - Graph Theory Problem I am trying to do Mathematics for CS course( 6.042) from MIT opencourseware. Could anyone please help me with this problem( from problem set 6. Problem 6).
Let G be a graph. In this problem we show every vertex of odd
degree is connected to at least one other vertex of odd degree in G.

(a) [6 pts] Let v be an odd degree node. Consider the longest walk starting at v that does
not repeat any edges (though it may omit some). Let w be the final node of that walk. Show
that w is not equal to v.
(b) [4 pts] Show that w must also have odd degree.
 A: HINT: Imagine walking along that walk, removing each edge of it as you go. Every time you go through a vertex (i.e., into it and out of it), you remove two of the edges at that vertex. Use that to show that if the vertex had even degree originally, you can never get stuck there: if the walk takes you into the vertex, it must also take you out again.
A: Question 1: Proof by contradiction
Suppose the w = v. That means in a walk there is no edge left going out of v such that we can walk on that edge. So, we walked on all the edges going out of v. So, for every time we went out of v, we were able to reach back to v(because w = v). That means v must be having even degree. We reached contradiction because v is having odd degree. So, w is not equal to v.
Question 2: Proof by contradiction
Suppose w is having even degree. So, the walk ending on the node with even degree. From w we cannot move further because all the edge have been visited from w. But every time walk enters w it must leave w because it has even degree. So, by that sense the last edge of the walk it enters w and does not leave. So, before the last edge whenever w was reached it was left, that shows even degree of w has been traversed but as the last time it was entered w it didn't left. So, it shows w has odd degree. Hence we reached contradiction
