Proof that a connected graph G(V,E) with |E| = |V| - 1 is a tree. Verify and Help

Question

there are two way's in my mind to proof this.

The first would be to proof with |E| = |V| - 1 that the graph can't have a cycle and therfore has to be a tree. Because a graph with a cycle has to have at least n nodes that are connected through n edges with each other. So |E| <= |V| must be true. Now that we know that the graph doesnt have a cycle and is connected it has to be a tree. Can i proof it this way?

The second way would be through induction. I would need here some help. |E| = |V| - 1 -> m = n - 1 Base: n = 1 m = 1 - 1 = 0 so there is 1 node without edge's so there can't be a cycle here, therefore the graph has to be a tree. Induction Hypothesis: the statement is valid for a k <= n and G is a graph without cycle's and is connectet -> G is a tree.

Induction Step: n+1 m = (n+1)-1 Here i need your help. How should i proof that there are no cycle's now?

Answer 1

Your first proof isn't really a proof. You've shown that a connected graph has a subgraph that satisfies $|E|=|V|$, yet that doesn't obviously violate $|E|=|V|-1$ in the full graph.

Instead you can use Euler's formula: $|V|-|E|+|F|=2$. Plugging your condition in gives $|F|=1$. Now convince yourself that a graph with a loop has $|F|\geq 2$ as the smallest loop (one that has no loops inside it) has at least an inner and outer face.

Answer 2

The first method is problematic because the cycle need not use all edges or vertices.

By induction, you can show

Claim. Every tree with $n$ vertices has $n-1$ edges.

Proof. If $n=1$, this is clear. Let $n>1$ and assume the claim holds for all smaller numbers of vertices. Clearly, the must be at least one edge (or else the graph is not connected). By removing an edge, the tree splits into two smaller connected graphs (why?), each of which is a tree. Let these have $n_1$ and $n_2$ vertices respectively, where $n_1+n_2=n$ and both $n_i$ are positive. Then the induction hypothesis applies to both, hence they have $n_1-1$ and $n_2-1$ edges, hence the original graph has $(n_1-1)+(n_2-1)+1=n-1$ edges. $\square$

Then it follows that

Corollary. Every connected graph on $n$ vertices that is not a tree has at least $n$ edges.

Proof. Starting from a connected non-tree, we can repeatedly remove an edge from a cycle without destroying connectivity. Sooner or later, after removing $k\ge 1$ edges, we will arrive at a tree. Hence we started with $n+k-1\ge n$ edges. $\square$