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?
1 Answer
$\begingroup$Consider the complete graph $K_5$: it has $5$ vertices, each of degree $4$, and how many edges?
$\endgroup$ 5
