HMIC

Combinatorics Difficulty 5.5 AIME, harder Prove it United States

Problem:

Let $G$ be a weighted bipartite graph $A \cup B$ , with $|A|=|B|=n$ . In other words, each edge in the graph is assigned a positive integer value, called its weight. Also, define the weight of a perfect matching in $G$ to be the sum of the weights of the edges in the matching.
Let $G'$ be the graph with vertex set $A \cup B$ , and contains the edge $e$ if and only if $e$ is part of some minimum weight perfect matching in $G$ .
Show that all perfect matchings in $G'$ have the same weight.

Solution

Solution:

Let $m$ denote the minimum weight of a matching in $G$ . Let $G''$ be the (multi)graph formed by taking the union of all minimum weight perfect matchings, but keeping edges multiple times. Note that $G''$ is regular. Now, assume that some perfect matching in $G'$ (equivalently $G''$ ) has weight $M > m$ . Delete this matching from $G''$ , and call the resulting graph $H$ . $H$ is still regular, so it can be decomposed into a union of perfect matchings. Now using pigeonhole directly gives us a contradiction.

To show that all regular bipartite graphs can be decomposed into a union of perfect matchings, use Hall's marriage lemma to take out one perfect matching and use induction.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.