Let $G$ be a graph with 8 vertices, 13 edges, $\delta(G)=2$ and $\Delta(G)=4$. Denote by $n_i$ the number of vertices in $G$ of degree $i$, where $i=2,3,4$. Assume that $n_3\ge1$. Find all possible answers for $(n_2, n_3, n_4)$. For each of your answers, construct a corresponding graph.
I know that the sum of all the degrees of the vertices must be even by the Hand-Shaking Lemma. I am pretty clueless as to how I can proceed as I am still new to this topic on graphs. Are there any combinatorial methods for this question or must I proceed by brute force, i.e. stating all possible cases for $n_i$? Some help will be deeply appreciated.
Best Answer
We can set up the following equations relating $n_2,n_3,n_4$ since there are 8 vertices and 13 edges: $$n_2+n_3+n_4=8$$ $$2n_2+3n_3+4n_4=2\cdot13=26$$ Subtracting twice the first equation from the second we get $$n_3+2n_4=10\tag1$$ All variables are positive integers ($\delta(G)=2$, $\Delta(G)=4$ and it is given that $n_3\ge1$). It is easy enough to list all the solutions to $(1)$ under this condition: $$(n_3,n_4)=(2,4),\ (4,3),\ (6,2)$$ From here $n_2$ can be found, but $(n_3,n_4)=(6,2)$ causes $n_2=0$, which has been excluded. Thus the only possible tuples $(n_2,n_3,n_4)$ are $$(2,2,4)\quad(1,4,3)$$ Here are explicit graphs corresponding to these degree sequences.