3
$\begingroup$

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?

  • 0
    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.2012-07-27
  • 1
    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).2012-07-27
  • 0
    a little bit more practice will clear my concepts... thank you!!!2012-07-27

1 Answers 1