I am supposed to prove that any graph that is connected and has v vertices and v-1 edges is a tree. I know this is a basic fact about trees, but i'm not sure why exactly it is.
[Math] Every connected graph with v vertices and v-1 edges is a tree
graph theorytrees
Related Question
- [Math] If $G$ is a connected graph with $n$ vertices and $n – 1$ edges then $G$ is a tree, using Induction.
- [Math] Relation between vertices and edges in a tree
- Prove that every complete graph with 4 or more vertices has two spanning trees with disjoint edges
- Smallest number of vertices of degree $1$ in tree with $3$ vertices of degree $4$ and $2$ of degree $5$
Best Answer
Let $V$ be set of vertices with $\#V\ge 2$. Then a minimal connected graph on $V$ is a connected graph in which if any edge is removed then the graph is no more connected.
Since the graph is connected it's sufficient to prove it is acyclic. Suppose there is a cycle $v_0\to v_1 \to \cdots \to v_n \to v_0$. Remove the edge $v_n \to v_0$, then any path that included the edge $v_n \to v_0$ can be reconstructed by replacing $v_n\to v_0$ by $v_n\to v_{n-1}\to \cdots \to v_0$, so the graph is still connected but with less edges - contradiction to minimality, so no cycles exist. Hence minimal connected graphs are trees.
Indeed, we can just remove edges one by one untill we cannot remove more without violating connectedness. Resulting subgraph of original graph is minimally connected.
Follows immediately.
Then you could prove the following:
Use induction on $n$ - consider you have a tree with $n$ vertices. Remove a leaf from the graph, and resulting graph is a tree with $n-1$ vertices, so you can do induction.
Finally, since your graph is connected and has $n$ vertices and $n-1$ edges, it contains a tree as a subgraph with $n$ vertices, which has $n-1$ edges. But your graph already has $n-1$ edges, and so your graph is minimally connected, so is a tree.