Will upvote if you explain and solve correctly!

Ex.2 (Euler's tour) In graph theory, an Eulerian path is a path in a finite graph G that visits every edge exactly once (allowing for revisiting vertices). Similarly, an Eulerian cycle is an Eulerian path that starts and ends on the same vertex. These were first discussed by Leonhard Euler while solving the famous Seven Bridges of Knigsberg problem in 1736 (See Figure 1). The exercise asks you to prove the following theorem, known as Euler's Theorem: "If a graph has an Euler cycle, then all of its vertices must have even degree." (the "degree" of a vertex u, often denoted du is the number of incident edges on the vertex u.) Then, describe an efficient algorithm to detect whether or not the graph has an Eulerian cycle. The algorithm should run in linear time (O(m+n), where G has m edges and n vertices. Figure 1: The Seven Bridges of Knigsberg. The city of Knigsberg in Prussia (now Kaliningrad, Russia) was set on both sides of the Pregel River, and included two large islands - Kneiphof and Lomse - which were connected to each other, and to the two mainland portions of the city, by seven bridges. Can you devise a walk through the city that would cross each of those bridges once and only once