Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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 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 at 21:04

3 Answers 3

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:

A graph with degree sequence $(7,7,7,7,7,7,7,5,5,5)$

So the minimum $n$-value is $10$.

share|improve this answer
    
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 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 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.$

enter image description here

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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