Path: utzoo!attcan!uunet!cs.utexas.edu!samsung!umich!sharkey!msuinfo!news
From: engelsma@buster.cps.msu.edu (Engelsma Jonathan)
Newsgroups: comp.theory
Subject: refs for graph problem wanted
Message-ID: <1990Oct30.181410.11143@msuinfo.cl.msu.edu>
Date: 30 Oct 90 18:14:10 GMT
Sender: news@msuinfo.cl.msu.edu
Distribution: na
Organization: Dept. of Computer Science, Michigan State University
Lines: 21


I've been told the following has been proven:

	Given a graph G, any two vertices u and v, and a maximum spanning tree
	T.  Let e be an edge with minimum weight w(e) on the path from u to
        v in T.  For any maximum spanning tree T' of G there will be a minimal
	edge e' on the path from u to v such that w(e') = w(e).   

Could somebody please give me a reference to where this proof was published.
Please e-mail your responses directly to me and if there is enough interest
I'll post a summary of responses.

Thanks in advance,
Jonathan

-------------------------------------------------------------------------
Jonathan R. Engelsma                            Michigan State University
E-mail:   engelsma@buster.cps.msu.edu                Department of
	  uunet!frith!engelsma	                   Computer Science
	  uunet!frith!jresys!engelsma (home)	
-------------------------------------------------------------------------