Let n, m be positive integers such that n+m is odd. Assume that the edges of a complete bipartite graph Kn,m are labeled by 1 and −1 such that the sum of the numbers written on all edges is zero. Show that this graph has a spanning tree such that the sum of the numbers on its edges is 0.
A spanning tree is a sub-tree of the graph that contains all the vertices.
Solution
We define an operation on spanning trees: we add an edge to it. This will certainly create a cycle. Now, we remove one of the edges of the cycle to obtain another spanning tree. The sum of the numbers written on the edges of the spanning tree changes by at most two. With this operation, it is possible to reach any spanning tree from any other spanning tree: Take an edge from the first tree that is not in the second tree, and add it to the second tree. In the cycle that is generated by this move, one edge does not belong to the first tree, because the first tree has no cycles. Remove that edge and continue until the two trees become one. Let T be a spanning tree, we define S(T) the sum of the numbers written on the edges of T. Based on discrete connectivity, it is sufficient to say that there is a tree T with S(T)≤0 and a tree T′ with S(T)≥0. To see this, note that the total sum of S(T) when T varies between all spanning trees is equal to the sum of the edges times the number of the spanning trees that include a specific edge. Therefore, the total sum is zero and there should be a tree T with S(T)≤0 and a tree T′ with S(T)≥0.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.
Source: MathNet,
licensed CC-BY-4.0.
Statement reproduced verbatim; metadata (topic, difficulty) added by this project.