Use induction on the number of edges to prove that every con

Use induction on the number of edges to prove that every connected graph contains a spanning tree. (Note that a spanning subtree is a subgraph T of G such that T is a tree and V(T) =V(G).)

Solution

number of edges that every connected graph contains a spanning tree

we know that spanning tree is a subgraph T of G such that T is a tree and V(T)=V(G)

if connected graph G has one edge

thus there should be two vertices

two edges with one edge denotes spanning tree

thus a connected graph containes a spanning tree

assume that for n edges conneted graph contains spanning tree

now for a connected graph has n+1 edges

remove one edge that does disturb the connectivity

now it has n edges connected graph

frm above assumption it contains spanning tree

therefore for n+1 connected graph contains spanning tree