Question 98
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.
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.