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

54 Views Asked by At

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

1

There are 1 best solutions below

0
On

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