1
$\begingroup$

Question is:

Let $G$ be a graph of 8 nodes and 15 edges in which each vertex is of degree 3 or 5. How many vertices of degree 5 does $G$ have? Construct one such graph $G$.

Answer: I think this cannot be done.

Edges = 15 means degree is 30, and if we divide 30 into 8 vertices such that each vertex is either of degree 3 or 5. By the rule, the number of odd vertices in any multigraph is even.

Let $V(G)=\{a,b,c,d,e,f,g,h\}$. Then:

$$ d(a) = d(b) = d(c) = d(d) = d(e)= 3 $$ $$ d(f) = d(g) = d(h) = 5 $$

Sum of degrees 30, but odd vertices are odd here.

Am I correct or is there any other way to solve this?

  • 0
    What do you mean "odd vertices are odd"? I count 8.2012-07-27

3 Answers 3