Number of graphs on $V = \left \{ 1,2,3,4,5 \right \}$ such that ${\rm deg}(1) ={\rm deg}(2)=2$

Question

I was trying to solve this by calculating different instances, for example - there is an edge between $\left\{ 1,2\right\}$ or if there isn't.

I think that the right way of solving this is by using the inclusion - exclusion principle, but I'm having a hard time breaking it down to cases.

Any help would be appreciated.

Answer 1

Among $\{3,4,5\}$ there are $3$ possible edges, hence $2^3=8$ different subgraphs. If $\{1,2\}$ is an edge there are $3\cdot3=9$ ways to draw second edges from $1$ and from $2$ to one of $\{3,4,5\}$. If $\{1,2\}$ is no edge there are also $3\cdot3$ ways to draw two edges each from $1$ and from $2$ to $\{3,4,5\}$. In all we obtain $8\cdot(9+9)=144$ different graphs of the desired kind.