# Proof for “A simple connected graph has n-1 edges iff it is a tree ” without induction.

I am trying to prove that a simple connected graph with n nodes has n-1 edges iff it is a tree.

I could prove it using induction but I was wondering if there is any other method.

As soon we add one more edge to a simple connected graph with n-1 edges it forms a cycle but I was not able to prove that.

• Do you mean a simple, connected graph? – Kevin Long Oct 29 '15 at 16:31
• What definition of tree are you using ? There are a couple so the proof depends on that... – Manuel Lafond Oct 30 '15 at 3:08
• A tree is a simple connected graph of without any cycles. – Shubham Ugare Oct 30 '15 at 16:39

If you remove the minimum spanning tree (MST) of $n-1$ edges (a simple connected graph has one) from a graph with $n$ edges (or more), you still have one edge.