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?

  • 3
    $\begingroup$ The complement of $5K_2$ is a description of your graph (which is correct). $\endgroup$ – Gordon Royle Oct 14 '18 at 21:55

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.

  • 1
    $\begingroup$ i of course did not in my actual answer introduce generality. But I, as a student of math in general, am interested in a general case answer as well. Hence, I talk about it here. I like the notion that the complement of $n/2 * K_2$ describes the graph for odd n offered by gordon. your answer works as well but only for my specific case. $\endgroup$ – rjm27trekkie Oct 14 '18 at 22:00
  • $\begingroup$ Yes, you could certainly let $n$ be even and go through the same proof showing that removing $\frac n2$ edges is necessary and sufficient. $\endgroup$ – Ross Millikan Oct 14 '18 at 22:02

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.