Another question in Graph Theory

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?

-
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

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). – 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

1 Answer

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

Solvitur ambulando:

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 9, "mathjax_display_tex": 2, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.3, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9253200888633728, "perplexity_flag": "middle"}