2
$\begingroup$

Find an Eulerian graph with an even/odd number of vertices and an even/odd number of edges or prove that there is no such graph (for each of the four cases).

I came up with the graphs shown below for each of the four cases in the problem. I know that if every vertex has even degree, then I can be sure that the graph is Eulerian, and that's why I'm sure about all the cases, except for the odd vertices, even edges case. Because as can be seen vertices, $3$ and $4$ have degree of $3$. So, any idea what that one is actually Eulerian graph? If no, can someone tell me whether an Eulerian graph can be found for the odd vertices, even edges case?

enter image description here enter image description here

$\endgroup$
0
$\begingroup$

Consider the complete graph $K_5$: it has $5$ vertices, each of degree $4$, and how many edges?

$\endgroup$
  • $\begingroup$ You mean like this: prntscr.com/8ux2ew - Cause like this, I count 9 edges, whereas I need even number of edges. $\endgroup$ – user72151 Oct 24 '15 at 20:46
  • $\begingroup$ @portal: You’re right; I wasn’t thinking clearly. I’ve fixed it now. $\endgroup$ – Brian M. Scott Oct 24 '15 at 20:47
  • $\begingroup$ Yep, $K_5$ has 5 vertices and 10 edges. And all the vertices have even degree. Thanks. $\endgroup$ – user72151 Oct 24 '15 at 20:56
  • $\begingroup$ @portal: You’re welcome. $\endgroup$ – Brian M. Scott Oct 24 '15 at 20:57
  • $\begingroup$ Can you please take a look at the following problem when you have time? math.stackexchange.com/questions/1506816/… $\endgroup$ – user72151 Oct 31 '15 at 20:48

Your Answer

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