# Max vertices in Odd Degree Graph

If I have a graph whose vertices all have odd degree greater than 1, what is the maximum possible number of vertices if the graph has at most 14 edges?

My thought for this is basically that your best case for odd degree being greater than 1 is 3, so you could use $2E\geq3n$ By this, I assumed the answer was 9, but I've been told 8 is the correct answer. Any ideas?

• You have $9$ as a theoretical maximum, now you need to consider if you can actually obtain a graph of that size with all vertices having odd degree greater than 1. What do you know about the degree sum of a graph? – Morgan Rodgers Nov 10 '17 at 7:11
• @MorganRodgers The degree sum should equal 2 * the number of edges and this should be greater than or equal to the number of regions. The number of regions seems to check out with Euler's formula. – Snowday313 Nov 10 '17 at 7:18

Observe that $n$ can not be odd. For if $n$ is odd, then $$3n=\text {odd number}$$ which is not possible in a graph as sum of degrees of all vertices should be an even number by hand-shaking lemma.
Thus $n=8$ and not $9$.
• @SantanaAfton Well eight vertices with degree $3$ won't give us a graph with $14$ edges. This is because $3\times 8=24 \neq 2 \times 14$. But six vertices with degree $3$ and two vertices with degree $5$ will surely give us $14$ edges since $3\times 6+5 \times 2=28=2 \times 14$. – Error 404 Nov 10 '17 at 8:44