Strongly maximal matchings in infinite graphs (Q1010872)

Summary: 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\left\{w(e) \mid e \in N \setminus M\right\} \leq \sum\left\{w(e) \mid e \in M \setminus N\right\}. \] 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.