# 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!

-
Is G a simple graph? If not, you could just sort of cheat and let there be loops from vertices to themselves. – Newb Feb 1 '14 at 20:27
Are multiple edges allowed between two vertices? Assuming so and with no loops, I was able to find an 8 vertex solution. – John Habert Feb 1 '14 at 21:04

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$.

-
Inscribe a triangle in a decagon to get a simple graph with degree sequence $(2,2,2,2,2,2,2,4,4,4)$. The complementary graph has degree sequence $(7.7.7.7.7.7.7.5,5,5)$. Is that your graph? Hard to see with all those lines. – bof Feb 1 '14 at 21:18
I don't know, but geng generated it along with many others with the same degree sequence. In any case, the Havel-Hakimi algorithm would also work in generating one. – Rebecca J. Stones Feb 1 '14 at 21:22

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.$

-

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$.

-