I've been trying to find the largest graph with 10 vertices such that each vertex has even degree. If the number of vertices, say $n$, were odd, then the answer is clearly just the complete graph $K_n$. Since $n$ is even in this case, I suppose that I must remove $\frac{n}{2}$ edges that will decrease the degree of each vertex by 1. I claim that I can do this for any complete graph $K_n$ and that for $n$ odd the maximal graph with all vertices of even degree is $K_n – \sum_{i=1}^{n/2} e_i$ where the edges $e_i$ satisfy the property that they decrease the degree of 2 vertices from $n-1$ to $n-2$.
Is my answer correct? Is there a better description of such a graph?
Best Answer
You should not introduce $n$ as we are just talking about $10$. Starting with $K_{10}$ and removing $5$ edges is a good approach. You need to show you can get a graph that has all vertices of even degree by removing $5$ edges, which you can do by making five pairs of vertices and removing the edges between the vertices in each pair. Then you need to show that removing five edges is necessary. If you remove fewer than five edges, you cannot remove an edge from each vertex and whichever vertex you did not remove an edge from will still have an odd degree.