0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Did you type b) correctly? Its impossible for a graph to have degrees of 2,3,4,4,6 as the total is odd. $\endgroup$ – Ian Miller Oct 13 '15 at 15:31
  • $\begingroup$ you are right. Sorry fixed it $\endgroup$ – user3015986 Oct 13 '15 at 15:34
  • $\begingroup$ @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). $\endgroup$ – Moritz Oct 13 '15 at 15:45
  • $\begingroup$ but can't it have individual edges springing out from one of the vertexes? What about loops? $\endgroup$ – user3015986 Oct 13 '15 at 15:48
  • $\begingroup$ 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 ... $\endgroup$ – Brian M. Scott Oct 13 '15 at 16:56
0
$\begingroup$

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."

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.