In my lecture of combinatory, there is this theorem :
T is a Tree $ \iff $ T has on edge less than the number of vertices and it is acyclic.
I'm confused because it appears to me that if there is at least a cycle in the graph, the graph must have the same number of edges and vertices... What do you think ? Do you have an example ?
On
Yes, I never noticed, but as you mentionned the condition acyclic can be replaced by "connected". It can easily be prooved by induction on $n$. We define the hypothesis : $$ \mathcal{H}_n : \{ \forall \text{ connected graph $G$ with } |E(G)|=n \text{ and } |V(G)|=n-1, \ G \text{ is a tree}\}$$
Base Case $n=1$. $G$ is an isolated vertex, i.e. a Tree
Induction Suppose $ \mathcal{H}_{n}$ is true, and let $G$ be a connected graph on $n+1$ vertices and $n$ edges.
Suppose that there is no vertices of degree 1, i.e. $\forall v\in V(G),\ d(v)\geq 2$. Then by hand-shaking lemma $$ 2m = \sum_{i=1}^{n+1}d(i)\geq 2(n+1)$$ in contradiction with our hypothesis on the number of edges.
Therefore $\exists \ u \in V(G)$ such that $d(u)=1$ (remember as $G$ is connected we cannot have $d(u)=0$). Then consider the graph $G'=G\backslash\{u\}$. It is a graph on $n$ vertices, $n-1$ edges (because $u$ had degree 1), and is still connected. Therefore by induction hypothesis, it is a Tree. Adding one vertex, connected to only one existing vertex in a tree, we cannot form a cycle, and then we built another tree. Therefore $G$ is also a Tree, and $\mathcal{H}_{n+1}$ is True.
Conclusion $ \mathcal{H}_{0}$ is true and $ \mathcal{H}_{n}\Rightarrow \mathcal{H}_{n+1}$, therefore $\mathcal{H}_{n}$ for all $n\in \mathbb{N}$
I guess sometime the acyclic condition is actually easier to check than the connectivity.
Consider the graph on 4 vertices $a,b,c,d$ which consists of a triangle on the vertices $a,b,c$, i.e., the edges are $ab,ac,bc$. It contains 4 vertices and 3 edges, yet isn't a tree.