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?
