Ask a Question

  1. Home
  2. Ask a Question
  3. Question Details
Doubts ?
Post a question
Ask Us

Categories

Prove that a simple graph G(V,E) has a spanning tree if G(V,E) is connected graph

on 2016-10-11 00:09:16   by Sudakhina   on MCA  1 answers

SHAKYA

on 2016-11-09 10:30:00  

Let G be a connected graph. If G has no circuit,then it is its own spanning tree. If G contains a circuit,then delete an edge from the circuit. The graph will still remain connected. If the graph thus obtained contains no circuit,it becomes a spanning tree of G. Otherwise repeat the operation till an edge from the last circuit is removed-giving a connected graph without any circuit. This left out graph contains all vertices of G as no vertice was removed in the deletion operation. So this left out tree is a spanning tree of G. Thus spanning tree of G is possible,only when G is connected.