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$

1 Answer 1

Reset to default
0
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ You mean like this: prntscr.com/8ux2ew - Cause like this, I count 9 edges, whereas I need even number of edges. $\endgroup$
    – user72151
    Commented Oct 24, 2015 at 20:46
  • $\begingroup$ @portal: You’re right; I wasn’t thinking clearly. I’ve fixed it now. $\endgroup$
    – Brian M. Scott
    Commented Oct 24, 2015 at 20:47
  • $\begingroup$ Yep, $K_5$ has 5 vertices and 10 edges. And all the vertices have even degree. Thanks. $\endgroup$
    – user72151
    Commented Oct 24, 2015 at 20:56
  • $\begingroup$ @portal: You’re welcome. $\endgroup$
    – Brian M. Scott
    Commented Oct 24, 2015 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
    Commented Oct 31, 2015 at 20:48

You must log in to answer this question.