# Is a simple graph connected, if every node has at least one adjacent edge and $|E|\ge |V|-1$?

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

Is the following statement true?
If $$|V|=n, |E|\ge n-1$$ and every node has at least one adjacent edge, then $$G$$ is connected.

I've proved 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 completed.

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?

If $$|V|=n, |E|\ge n-1$$ and every node has at least one adjacent edge , then $$G$$ is connected. Exercise. Construct a simpler counterexample where $$|V|=n$$ and $$|E|=n-1$$.