Graph with vertices having certain degrees Let $G$ be a simple graph with $n$ vertices, such that $G$ has exactly $7$ vertices of degree $7$ and the remaining $n-7$ vertices of degree $5$. What is the minimum possible value for $n$?
I have gotten that $n$ could equal $14$ with $G$ as the following graph:
i) $G=G_1 \cup G_2$
ii) $|G_1|=|G_2|=7$
iii) $G_1 \cong K_7$
iv) each vertex in $G_2$ is connected to one distinct vertex in $G_1$ and four more in $G_2$ (subject to the restraints)
How do I know this is the least value of $n$? If it is not, how can I compute the least value? Thank you!
 A: We must have an odd number of $5$-degree vertices to satisfy the Handshaking Lemma.
We can exclude the possibility of degree sequence $(7,7,7,7,7,7,7,5)$ since every $7$-degree vertex must be attached to the $5$-degree vertex, giving a contradiction.
A graph with degree sequence $(7,7,7,7,7,7,7,5,5,5)$ is illustrated below:

So the minimum $n$-value is $10$.
A: Assuming you are concerned with simple graphs, you can use the Erdos-Gallai theorem that characterizes when does a graph sequence admit a graphical representation.
Using the above theorem you can verify that you need at least three vertices of degree $5$ thus giving you the degree sequence $ds = (7,7,7,7,7,7,7,5,5,5).$ Given this you can construct the following graph realizing  $ds.$

A: Since all the degrees are odd, the total number of vertices must be even, so the number of vertices of degree $5$ must be odd.
With just one vertex of degree $5$ the degree sequence is $(7,7,7,7,7,7,7,5)$; then the complementary graph has degree sequence $(0,0,0,0,0,0,0,2)$, which is impossible.
So let's try for a graph with degree sequence $(7,7,7,7,7,7,7,5,5,5)$. The degree sequence of the complementary graph would be $(2,2,2,2,2,2,2,4,4,4)$. This is easily realized: start with a $10$-cycle, pick three nonadjacent vertices, and join them to one another with edges.
So the minimum possible value of $n$ is $10$.
