Strongly Maximal Matchings in Infinite Graphs

Abstract

Given an assignment of weights $w$ to the edges of an infinite graph $G$, a matching $M$ in $G$ is called strongly $w$-maximal if for any matching $N$ there holds $\sum\{w(e) \mid e \in N \setminus M\} \le \sum\{w(e) \mid e \in M \setminus N\}$. We prove that if $w$ assumes only finitely many values all of which are rational then $G$ has a strongly $w$-maximal matching. This result is best possible in the sense that if we allow irrational values or infinitely many values then there need not be a strongly $w$-maximal matching.