4
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ 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? $\endgroup$ May 7 '19 at 9:11
1
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ The error in the original post is that it is possible for two of the variables to be equal to zero. Those three cases were subtracted twice. $\endgroup$ May 6 '19 at 23:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.