1
   

Another Hard One!!!

 
 
RK4
 
Reply Wed 5 Oct, 2005 08:42 pm
Let T_1 and T_2 be spanning trees of a connected graph G.

(i) If e is any edge of T_1, show that there exists an edge f og T_2 such that the graph (T_1 - {e}) U {f} (obtained from T_1 on replacing e by f) is also a spanning tree.

(ii). Deduce that T_1 can be 'transformed' into T_2 by replacing the edges of T_1 one at a time by edges of T_2 in such a way that a spanning tree is obtained at each stage.
  • Topic Stats
  • Top Replies
  • Link to this Topic
Type: Discussion • Score: 1 • Views: 478 • Replies: 0
No top replies

 
 

Related Topics

Evolution 101 - Discussion by gungasnake
Typing Equations on a PC - Discussion by Brandon9000
The Future of Artificial Intelligence - Discussion by Brandon9000
The well known Mind vs Brain. - Discussion by crayon851
Scientists Offer Proof of 'Dark Matter' - Discussion by oralloy
Blue Saturn - Discussion by oralloy
Bald Eagle-DDT Myth Still Flying High - Discussion by gungasnake
DDT: A Weapon of Mass Survival - Discussion by gungasnake
 
  1. Forums
  2. » Another Hard One!!!
Copyright © 2024 MadLab, LLC :: Terms of Service :: Privacy Policy :: Page generated in 0.03 seconds on 06/22/2024 at 08:52:49