Let $ G=(V,E)$ be an undirected graph without self-loops or parallel edges.

Does the statement:

If $ |V|=n, |E|\ge n-1$ and every node has at least one adjacent edge , then $ G$ is connected;

hold?

I’ve proofed it for $ |E|=n-1$ :

Per induction:

Start:

For $ \left|V\right|=1$ the graph is trivially connected.

Induction step:

Let the statement be shown for all graphs $ G=\left(V,E\right)$ where $ \left|V\right|=n-1$ and $ |E| = n-2$ .

Let further $ G=\left(V,E\right)$ with $ \left|V\right|=n$ and $ |E| = n-1$ be given.

We’re now looking for an induced sub graph $ G|_{V^\prime}$ where $ V^\prime\subset V, \left|V^\prime\right|=n-1$ , so that $ G|_{V^\prime}$ has at least $ n-2$ edges.

(Any such sub graph can have at most $ n-2 $ edges, as there’ll always be at least one edge that originally lead to the removed node)

Let’s now assume that every sub graph $ G|_{V^\prime}$ has less than $ n-2$ edges.

Then, the removed node in any sub graph would have at least $ 2$ edges.

Thus, every node must have at least $ 2$ edges, and therefore there’d have to exist at least $ n$ edges in the graph.

Therefore, there’s at least one sub graph $ G|_{V^\prime}$ with $ n-2$ edges, for which our induction assumption holds. And because there is one edge from $ G|_{V^\prime}$ to the erased edge, we get that $ G$ is connected.

Therefore, the induction is proven.

However, if I try to generalize the above proof, the same style leads to an inequality that only holds if $ |E|>|V|$ .

Therefore, if the above proof can be generalized, how would it look? If not, what’s an example where it fails?