Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Question: Let $H$ be a graph of order 10 such that $3\le d(v)\le5$ for each vertex $v$ in $H$ [where $d(v)$ is the degree of $v$]. Not every vertex is of even degree. No two odd-degree vertices are of the same degree. What is the size [number of edges] of $H$?

Answer: Size of $H$ is 20

let $V(H)=\{{a,b,c,d,e,f,g,h,i,j\}}$, then $$d(a)=3, d(b)=4, d(c)=4, d(d)=4, d(e)=4, d(f)=4, d(g)=4, d(h)=4, d(i)=4,$$ $$d(j)=5$$

Sum is 40

hence size is 20

Am I correct?

share|cite|improve this question
Yes, you only have the possible degrees 3, 4 and 5. There's at least one odd degree vertex (so there must be at least two), but no two odd-degree vertices can have the same degree, so there must be exactly one of degree 3 and one of 5. Then the rest must be degree 4. – Luke Mathieson Jul 27 '12 at 10:48
There's a step missing from the argument in Luke's argument. It's also necessary to show that such a graph does indeed exist; presumably by drawing it (or describing it fully). – user22805 Jul 27 '12 at 11:37
a little bit more practice will clear my concepts... thank you!!! – Intellectual_ Jul 27 '12 at 11:38

You've done all the hard work. Now all that remains is to show that such a graph exists.

Solvitur ambulando:

enter image description here

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.