I should prove this claim:
Every undirected graph with n vertices and $2n$ edges is connected.
If it is false I should find a counterexample.
I was thinking to consider the complete graph with $n$ vertices. Such a graph is connected and contains $\frac{n(n-1)}{2}$ nodes. Considering that $2n > \frac{n(n-1)}{2}\implies$ my graph is connected too. But I'm not sure this could be a solution because even my graph has $2n$ edges it doesn't have to be complete.
Can anybody help me?
Best Answer
Consider two copies of graphs with $m$ vertices amd $2m$ edges, e.g. of $K_5$, the complete graph with $m=5$ vertices. With two copies, you have $n=2m$ vertices and $2n$ edges, but the graph is not connected. Therefore the claim is false.