# Does the graph have an Euler's circuit?

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?

• Did you type b) correctly? Its impossible for a graph to have degrees of 2,3,4,4,6 as the total is odd. – Ian Miller Oct 13 '15 at 15:31
• you are right. Sorry fixed it – user3015986 Oct 13 '15 at 15:34
• @user3015986: How can a graph with 5 vertices have a vertex of degree 6? In my opinion there is no such graph in b) and c). – Moritz Oct 13 '15 at 15:45
• but can't it have individual edges springing out from one of the vertexes? What about loops? – user3015986 Oct 13 '15 at 15:48
• If the graphs are not required to be simple, there is a connected graph with $5$ vertices of degrees $2,2,4,4$, and $6$. It has loops at the vertices of degrees $4$ and $6$; the vertex of degree $6$ is adjacent to each of the other $4$ vertices; the vertices of degree $2$ are adjacent to each other; and the vertices of degree $4$ are adjacent to each other. Alternatively, you can do it without loops but with multiple edges: run two edges from the vertex of degree $6$ to each of the vertices of degree $4$ and one to each of the vertices of degree $2$, connect each vertex of degree $4$ to ... – Brian M. Scott Oct 13 '15 at 16:56