Problem

Source: Iran 2024 3rd round combinatorics exam P3

Tags: combinatorics, graph theory



$m,n$ are given integer numbers such that $m+n$ is an odd number. Edges of a complete bipartie graph $K_{m,n}$ are labeled by ${-1,1}$ such that the sum of all labels is $0$. Prove that there exists a spanning tree such that the sum of the labels of its edges is equal to $0$.