I need to prove that

In a simple graph $G$, if all the $n$ vertices have a degree of at least $4$, then the number of edges is at least twice the number of vertices.

I already know that $\deg(n) = 2E$.

Then for the question $$\deg(n) \ge 4 = 2E$$

but then I couldn't solve further.


Hint: if you add up the degrees of all the vertices, you've counted each edge twice.


i already know that deg(n) = 2E then for the question deg(n)>=4 = 2E

Try to be as precise as possible. What is $E$ here? What is $\deg(n)$? Are you referring to the fact that $$ \sum_{v \in V} \deg(v) = 2|E|, \tag{1} $$ where $V$ is the set of vertices and $E$ Is the set of edges? (Here $|E|$ means the size of set $E$, that is, the number of edges.)

but then i couldent solve more

If you are stuck, a good place to start is the above equation (1). There is a $\deg(v)$ in that equation. What do you know about $\deg(v)$? There is also a $|E|$ in that equation -- that's good, because you are trying to show something about the number of edges. You want to relate the number of edges to the number of vertices. So, you should be looking for a way to use what you know about $\deg(v)$ to get something in terms of the number of verticies, $|V|$.

  • $\begingroup$ yes that is the formula i am referring to I only know that the vertices in that graph are of degree 4 or more , so i could say that 4n =2|E| then 2n=|E| ? $\endgroup$ – Sh Alkaa Dec 7 '18 at 18:22
  • $\begingroup$ @ShAlkaa Great! Try what I suggested if you are stuck. Does it help? $\endgroup$ – 6005 Dec 7 '18 at 18:24
  • $\begingroup$ should i consider the degrees as 4n =2|E| then 2n=|E| ? $\endgroup$ – Sh Alkaa Dec 7 '18 at 18:47
  • $\begingroup$ @ShAlkaa What do you mean "consider the degrees as 4n = 2|E|"? Start from equation (1). $\endgroup$ – 6005 Dec 7 '18 at 18:54
  • $\begingroup$ i couldn't understand how to start from equation 1 could you explain more, please ? $\endgroup$ – Sh Alkaa Dec 7 '18 at 19:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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