Each of the following describes a graph. In each case answer yes, no , or not necessary to this question.
Does the graph have an Euler's circuit? Justify your answer.
a) G is a connected graph with 5 vertices of degrees 2,2,3,3 and 4
b) G is a connected graph with 5 vertices of degrees 2,2,4,4 and 6.
c) G is a graph with 5 vertices of degrees 2,2,4,4 and 6
My attempt:
a) No because it has at least one vertex with an odd degree
b) No because the graph isn't connected? A connected graph can only have a max
degree of one less than the number of vertices.
c) So I'm guessing this graph isn't connected. But then it means it can be a simple graph but also have parallel edges/ loops?
Best Answer
To be Eulerian a graph must be connected and must have even order of all vertices.
a) Two odd vertices so not Eulerian (but it is semi-Eulerian).
b) All even vertices so Eulerian.
c) All even vertices so might be Eulerian, but you are not told that it is connected. Therefore answer is "not necessarily Eulerian."