My Math Forum  

Go Back   My Math Forum > Math Forums > Math

Math General Math Forum - For general math related discussion and news


Thanks Tree1Thanks
  • 1 Post By gyarenas1
Reply
 
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_1-a_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!
Thanks from manus
gyarenas1 is offline  
 
Reply

  My Math Forum > Math Forums > Math

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 k-partite 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





Copyright © 2019 My Math Forum. All rights reserved.