Question of Graph Theory

Question

Question is: Let G be a graph of order 8 and size 15 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. size = 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)=3 d(b)=3 d(c)=3 d(d)=3 d(e)=3 d(f)=5 d(g)=5 d(h)=5

---

SUM=30 but odd vertices are odd here

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

Answer 1

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:

Answer 2

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.

Answer 3

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?