Graph with 8 nodes and 15 edges and degrees restricted to 3 or 5

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?

-
What do you mean "odd vertices are odd"? I count 8. – user22805 Jul 27 '12 at 9:41

How about if you have 5 vertices $a_1,\ldots,a_5$ and 3 vertices $b_1,b_2,b_3$. Now draw an edge joining each of the $a_i$ to each of the $b_i$. Surely this meets the required criteria?

-
yes this is easy! i still need lots of practice to solve such problems!!! Thank you! – Intellectual_ Jul 27 '12 at 9:51
You also made a parity mistake, you have an even number of odd-degree vertices, as David Wallace showed they easily form a $K_{3,5}$. I think that miscount was probably the source of the problem. – Luke Mathieson Jul 27 '12 at 9:51
hmm... i was wrong! vertices are 8 and not odd... – Intellectual_ Jul 27 '12 at 9:53
grr... i m still confused... all 8 vertices are odd, that means they are either 3 or 5 and number of vertices is even that is 8 so this question was possible but i did not understand... – Intellectual_ Jul 27 '12 at 10:17

I'm not sure if you meant to use the word "multigraph" in your write-up. Let's stick to a simple graph $G$ with 8 vertices and 15 edges.

Now each edge meets two distinct vertices, so the sum of all vertex degrees is twice 15 or 30. That gives us two equations for these unknowns:

$$x := \text{number of vertices of degree 3}$$ $$y := \text{number of vertices of degree 5}$$

$$x + y = 8$$ $$3x + 5y = 30$$

We can solve this linear system to determine that $x = 5$ and $y = 3$.

Although we cannot deduce the entire structure of $G$, one possibility has been pointed out by David Wallace: the complete bipartite graph $K_{5,3}$. You can easily move some edges around to modify that example into others that are not bipartite.

-

We can generate a complete list of non-isomorphic $8$-vertex $15$-edge graphs with degrees between $3$ and $5$ using geng which comes with nauty. The command is:

geng 8 15:15 -d3 -D5


Using a script, we can print out the graphs without degree $4$ vertices. Here are the possibilities:

-