$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$.
Problem
Source: Iran 2024 3rd round combinatorics exam P3
Tags: combinatorics, graph theory
29.08.2024 23:25
Discrete continuity helps here. Let $X$ be the set of spanning trees. Let $E$ be the set of edges. For each spanning truee $T$, let $s(T)$ be the sum of the labels of the edges of $T$. Moreover, for each edge $e$, let $l(e)$ be its label. By symmetry, each edge participates in the same number of spanning truees, call it $c$. Hence $$\sum_{T\in X} s(T)=c\sum_{e\in E}l(e)=0.$$Hence there exist spanning trees $T,U\in X$ such that $s(T)\le 0\le s(U)$. We now perform the following algorithm by definining a sequence $T_n$ of spanning trees. We initially define $T_1=T$. At step $i$, if $T_i=U$, the algorithm terminates. Otherwise assume $T_i\ne U$. Pick an edge $e\in E(U)\setminus E(T_i)$. Add $e$ to $T_i$. Now $T_i$ contains a single cycle $C$. Since $U$ does not contain a cycle, there exists an edge $e'\in C$ not in $U$. Now we remove $e'$ and we obtain a spanning tree, which will be define as $T_{i+1}$. This way, the number of common edges of $T_i,U$ strictly increases so the algorithm must terminate in a finite number of steps. Since each spanning tree consists of $m+n-1$ edges, the sum of its labels must be even. Moreover, since $T_i$ and $T_{i+1}$ differ in one edge, the difference $s(T_{i+1})-s(t_i)$ is $-2$, $0$ or $2$. Let $p$ be the positive integer such that $T_p=U$. Since $s(T_1)\le 0\le s(U)=s(T_p)$ and the difference at each step never exceeds $2$ and is always even, there exists $i\in[1,p]$ such that $s(T_i)=0$, as desired.