A simple problem of graph theory about the degree of vertices.

Question

A graph has $7$ vertices and $10$ edges then which is true?

$(I).3$ vertices of degree $4$ and $4$ vertices of degree $2$.

$(II).2$ vertices of degree $5$ and $5$ vertices degree $2$.

$(III).$Every vertex of degree $5$.

My try:Since the number of odd degree vertices is always even so the last option is false.

About other two options I do not know whether such graphs exist or not.I also try the formula $$\sum_{v\in V}d(v)=2|E|$$

But this is satisfied in the first two options.

Answer 1

Try to draw graphs which satisfy conditions I and II. If you are successful, you can rule out that case, and if not, this may help you realize why that case is impossible.

Answer 2

It’s not hard to construct a graph with $2$ vertices of degree $2$ and $5$ of degree $2$; you should try to do so. That suggests that you should try to show that (I) is impossible.

However, the problem is defective, because (I) is actually also possible. Let the vertices be $x,y,z,a,b,c$, and $d$, and let the edges be $xy,yz,xa,za,xb,zb,xc,yc,yd$, and $zd$. If you check, you’ll find that $x,y$, and $z$ have degree $4$, while $a,b,c$, and $d$ have degree $2$.

Answer 3

If you have a simple graph you can always know if your statements are true or not since the sum of the degrees of all vertices always have to be less than $n(n-1)$. This is the extremal case where you have a complete graph and no more edges can be added.