Good morning everyone. I failed a graph theory exam last week and I would like to know how to solve some of the problems I got because I don't have any idea. They were mainly proofs and I am very bad at this. The problem is:
Let $G = (V,E)$ be a convex graph, with $e : E \rightarrow \mathbb{R}$ being a cost function, $A$ is a cut in $G$ and $e \in A$ is the only minimum cost edge from $A$. Proof that $e$ is found in every minimum spanning tree from $G$.
I didn't have any idea, tried to say that a min cut has a spanning tree or something like this. I know it may sound strange. Would you like to help me out please?
Thank you very much and I wish you all a nice day.
I think you mean connected, not convex graph.
A cut-set is a set of edges, leaving them causes the increase of the number of components. A cut-set is a cut if any of its real subsets are not cut-sets. Considering G is connected, we can exactly divide the vertices of G into 2 connected parts, based on the cut A. Each edge from A has endpoints from both partitions at same time.
The spanning tree should have exactly one edge from A. One edge is needed to connect the 2 parts. If it had more than 1, there would be multiple ways between the 2 partitions, because 1 edge could already connect them together. It would mean a circle, that cannot exist in a tree.
Let's suppose that we have a minimal spanning tree T of graph G without e. Call f the edge from A, which certainly costs more than e. T is also connected as G were. Remove f from T. Now the vertices are divided into 2 parts as mentioned above. We got 2 subgraph, which are also trees. Since e is an element of the cut A, its endpoints are in the different partitions. So adding e to T connects the graph again.
It is a tree, as a result of connecting 2 trees. Also a spanning tree being every vertices connected as in T was.
Because we replaced a higher cost edge with a lower one, T could not be a minimal spanning tree.