# Graph theory and combinations

Graph $$G$$ has 9 vertices and 21 edges. 3 vertices have degree $$x$$, 3 have degree $$y$$, and 3 have degree $$z$$. Where $$x,y,z$$ are allowed to be the same number.

a) How many graph G could satisfy these criteria?

My work:

Total deg (G) = 3x+3y+3z = 2 * 21

3x + 3y + 3z = 42

x + y + z = 14

All the different possibles values that x, y, and z can have to satisfy x + y + z = 14 are 16 choose 14. So there are 120 G graphs that could satisfy these criteria.

b) How many graphs G could satisfy these criteria if G has no isolated vertices?

My work:

If G has no isolated vertices then,

x + y + z = 14, where x, y, and x are equal or greater than 1.

Hence, I thought that since I already know there are 120 possible G graphs (where x,y,z can be equal to 0). Then I could just count the possible ways x + y + z = 14 when x = 0 + when y = 0 + when z = 0; and then subtract that value from 120 to get the total possible ways x + y + z = 14 if x,y,z are greater than or equal to 1. My answer was 75...

Am I doing something wrong?

• I hope the original question does not actually ask how many possible graphs there are. Surely for each particular set of values $x$, $y$, $z$ there are many possible distinct graphs with those vertex degrees? May 7 '19 at 9:11

You've made some kind of error in the second case. If we write \begin{align}X&=x-1\\Y&=y-1\\Z&=z-1\end{align} then we get $$X+Y+Z=11$$, so that there are $${13\choose11}=78$$ possibilities.