Which of the following is non-Eulerian but follows a Euler path?

Question

Image - https://imgur.com/a/JiJWEJm

CHOICES:

a. G1 and G2

b. G4

c. G3 and G1

Answer 1

A graph is Eulerian if it has an Eulerian cycle: a cycle that visits every edge exactly once. It turns out that Eulerian graphs are those where every vertex/node has an even number of edges coming into it (i.e. every vertex/node has even degree).

Graphs with Eulerian paths, on the other hand, are those where every vertex/node has even degree except, possibly, two nodes (those where an Eulerian path starts/ends). Every Eulerian graph has an Eulerian path (that starts/ends at the same vertex/node), but graphs with exactly two odd degree vertices/nodes have an Eulerian path but are not Eulerian.

Take a look at the graphs again, checking whether each has all but two nodes of even degree.