No help from the urgent help section... I just need ONE example that fails to disprove it! ONE!
Originally Posted by redsoxfan620
"Consider an undirected graph G with capacities on the edges. The flow capacity between vertices u and v is defined to be the maximum flow attainable between u and v. Prove or disprove: there exists a spanning tree T which is a sub-graph of G with edge capacities (not necessarily the same as those in G) that preserves the flow capacities for every pair of vertices."
So this is the problem I have spent about 8 hours on and done hundreds of examples. According to the teacher it is possible to disprove with a "small counter-example." But after hundreds of attempts I have still failed to come up with one that does not work.
My understanding is, for example, if I had a square with vertices A, B, C, and D, I would have to find an example where the flow from A to B, A to C, A-D, B-C, B-D, C-D cannot be maintained in a spanning tree. The only way, it seems to me, that this is possible is if there are an equal number of unique flow numbers as there are nodes, since a spanning tree must have n-1 edges ... but thus far I can't find a single one where this is the case.