-2
$\begingroup$

We know that the converse is true, any connected graph $G = (V, E)$ must have $|E| \geq |V| − 1$.

$\endgroup$
  • 1
    $\begingroup$ What are your thoughts on the problem? Did you try any small cases? Is anything special about G? Is it simple? $\endgroup$ – JavaMan Mar 23 at 20:52
2
$\begingroup$

No, it is not. Take for example a complete graph on $5$ vertices. (A "complete graph" is one with all possible edge.) This has $\binom 52 = 10$ edges. Now simply add an isolated vertex. The new graph has $6$ vertices and $10 > 5$ edges

$\endgroup$

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.