I have to prove that a cycle free graph $|E| = |V|-1$ is a tree, ($|E|$ : #edges, $|V|$ : #vertices). I used induction for it.
Base case: Let $G=(V,E)$ be a cycle free graph with $|E|=n$ and $|V|=n+1$. For $n = 1$ we get a graph with $1$ edge and two vertices so the graph is cycle free and connected $\Longrightarrow$ by def a tree.
IH: Let the statement be true for all graphs $G=(V,E)$, $|E|\leq n$, $|V|\leq n+1$
IS: Let $G=(V,E)$ be a cycle free graph with $|E|= n+1$ and $|V|=n+2$. Since $G$ is cycle free and $|E|<|V|$ there must be a vertex $v$ with degree $1$. Vertex $v$ has just one incident edge $e$, build a graph $G'$ with G without $v$ and $e$. So $G'$ has $|E|=n$ and $|V|=n+1$ because of IH $G'$ must be cycle free and connected so $G'$ is a tree, if you take $G'$ and put $v$ and $e$ in it to build $G$ again, you would still have a tree because you couldn't create a cycle and it still would be connected so $G$ must be also a tree.
Would this proof by induction be correct?
I also thought of a proof by contradiction.
Suppose $G=(V,E)$ is not a tree, then $G$ has to have more than one component because $G$ is cycle free and $|E| = |V|-1$ applies. Because of those properties $G$ cant have more than one component and must be connected $\Longrightarrow$ a tree. I'm not sure if the last part is enough.
2026-04-02 02:28:54.1775096934