0
$\begingroup$

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.

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

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.

Between the vertices of this edge, a path should be in the MST, forming a cycle in the original graph.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.