# If a graph $G = (V, E)$ has $|E| \geq |V| − 1$, is it connected?

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

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

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