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

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?

  • 0
    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...2012-07-27
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.

2

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:

The <span class=8-vertex $15$-edge graphs with vertices of degrees $3$ and $5$.">