An Eulerian tour in an undirected graph is a cycle that is allowed to pass through each

QUESTION:

An Eulerian tour in an undirected graph is a cycle that is allowed to pass through each vertexmultiple times, but must use each edge exactly once.This simple concept was used by Euler in 1736 to solve the famous Konigsberg bridge problem,which launched the field of graph theory. The city of Konigsberg (now called Kaliningrad, inwestern Russia) is the meeting point of two rivers with a small island in the middle. There areseven bridges across the rivers, and a popular recreational question of the time was to determinewhether it is possible to perform a tour in which each bridge is crossed exactly once.Euler formulated the relevant information as a graph with four nodes (denoting land masses)and seven edges (denoting bridges), as shown here.Notice an unusual feature of this problem: multiple edges between certain pairs of nodes.(a) Show that an undirected graph has an Eulerian tour if and only if all its vertices have evendegree. Conclude that there is no Eulerian tour of the Konigsberg bridges.(b) An Eulerian path is a path which uses each edge exactly once. Can you give a similarif-and-only-if characterization of which undirected graphs have Eulerian paths?(c) Can you give an analog of part (a) for directed graphs?