-1
$\begingroup$

) Suppose G is a simple graph with n vertices. Prove that G has twice as many edges as vertices only if n ≥ 5. ?

Any one can help?

$\endgroup$
0
$\begingroup$

Prove that G has twice as many edges as vertices only if n ≥ 5

Rephrased: prove that if $n < 5$, $G$ has fewer than $2n$ edges.

Which simple graph on $n$ vertices has the most edges? How many does it have, as a function of $n$?

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ i think n ≥ 5. already i dont know the answer ! $\endgroup$ – Fatema Ali May 9 '18 at 9:05
0
$\begingroup$

in a graph sum of the degree= 2* number of edges. Let n < 5 then sum of degree is at most n(n-1), so number of edges is at most n(n-1)/2. Let f(n)= n(n-1)/2. It is easy to show that f(n)<= 2n when n<5.

| cite | improve this answer | |
$\endgroup$

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