
Math General Math Forum  For general math related discussion and news 
 LinkBack  Thread Tools  Display Modes 
July 15th, 2016, 07:00 AM  #1 
Newbie Joined: Jul 2016 From: China Posts: 1 Thanks: 1 Math Focus: Graph Theory  A graph theory problem about spanning tree
Proposition. Given a simple connected graph G, suppose T_1 and T_2 are two different spanning trees of G and E(T_1)\E(T_2)={a_1, a_2, ..., a_s}, E(T_2)\E(T_1)={b_1, b_2, ..., b_s}. Then, there exist a permutation {p_1, p_2, ..., p_s} such that T_1a_i+b_{p_i} (i = 1, 2,...,s) is still a spanning tree of G. Is the above proposition true? If it is, how to prove? Thanks! 

Tags 
graph, problem, spanning, theory, tree 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
A graph problem in graph theory!  lubna_mira  Applied Math  0  January 12th, 2014 01:52 PM 
Spanning kpartite graph  kriegor  Applied Math  1  April 12th, 2013 11:06 AM 
Need pointer to an algorithm  might be a spanning tree, not  gerry  Applied Math  0  March 29th, 2013 08:15 PM 
Vertices of Tree Graph Theory  jakkals  Applied Math  0  August 21st, 2012 03:26 AM 
Graph theory proof (uniqueness of minimum spanning tree)  aeromantang  Applied Math  3  December 28th, 2011 10:34 AM 