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?

  • 2
    $\begingroup$ 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? $\endgroup$ – Morgan Rodgers Nov 10 '17 at 7:11
  • $\begingroup$ @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. $\endgroup$ – Snowday313 Nov 10 '17 at 7:18

As mentioned in the comments by Morgan Rodgers,

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$.

  • $\begingroup$ How do we know there is a construction for eight vertices? $\endgroup$ – Santana Afton Nov 10 '17 at 7:39
  • $\begingroup$ @SantanaAfton I believe you'll find that the setup with 8 vertices and 14 edges satisfies both Euler's method and its corollary. $\endgroup$ – Snowday313 Nov 10 '17 at 7:51
  • $\begingroup$ @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$. $\endgroup$ – Error 404 Nov 10 '17 at 8:44

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.