# Understanding characterizations of Matching on Graphs

I am studying Matching Theory on Graphs and I am wondering if I understand the characterization of the problems right.

Definition: Let $G = (V, E)$ a graph. A set $M \subseteq E$ is called a matching in $G$ if and only if each vertex $v$ in $V$ is incident to at most one edge in $M$, that is, $\forall v \in V ( \forall w \in V ( \forall x \in V (( vw \in M \wedge vx \in M) \rightarrow w = x)))$ holds. Edges may be weighted. For any matching $M$ and weight function $w: E \rightarrow \mathbb Q$ we define $w(M) := \Sigma_{e \in M} w(e)$.

In the following are the definitions of the two computational problems I am currently working with. For simplicity sometimes I use bipartite graphs only.

Problem Name: $\text{MAXIMUM-CARDINALITY MATCHING}$

Input: A graph $G = (V, E)$.

Task: Find a matching $M$ such that $|M|$ is maximum.

Problem Name: $\text{MAXIMUM-WEIGHT BIPARTITE MATCHING}$

Input: A bipartite graph $G = (V, E)$ with weights $w: E \rightarrow \mathbb Q$ on the edges.

Task: Find a matching $M$ such that $w(M)$ is maximum.

Definition: A path $P$ in $G$ is called $M$-alternating if and only if the edges in $P$ are alternatingly out of and in $M$.

Definition: A path $P$ in $G$ is called $M$-augmenting if and only if $P$ is $M$-alternating and both its end vertices are not covered by $M$.

Thoerem (I think it is due to Peterson): Let $G = (V, E)$ be a graph and let $M$ be a matching in $G$. Then either $M$ is a solution to $\text{MAXIMUM-CARDINALITY}$ $\text{MATCHING}$ or there exists an $M$-augmenting path.

Theorem (Egervary): Let $G = (V, E)$ be a bipartite graph and let $w: E \rightarrow \mathbb Q$ be a weight function. Then the maximum weight of a matching in $G$ (that is, the weight of a solution to the $\text{MAXIMUM-WEIGHT}$ $\text{BIPARTITE MATCHING}$ problem) is equal to the minimum value of $y(V)$, where $y : V \rightarrow \mathbb Q$ is such that $y_u + y_v \geq w_e$ for each edge $e = uv$. If $w$ is integer, we can take $y$ integer.

My question is: Does there exist a simpler characterization of the $\text{MAXIMUM-WEIGHT}$ $\text{BIPARTITE MATCHING}$ problem similar to Peterson's Theorem? What is wrong with the following characterization?

First, let $A \; \Delta \; B$ denote the symmetric difference of two sets $A$ and $B$. Further, if $P$ is a path, then let $E(P)$ denote the set of edges in $P$.

Hypothesis: Let $G = (V, E)$ be a bipartite graph, $w: E \rightarrow \mathbb Q$ a weight function, and $M$ a matching in $G$. Then either $w(M)$ is maximum or there exists an $M$-alternating (note: not necessarily $M$-augmenting) path $P$ such that $M' := M \; \Delta \; E(P)$ is a matching in $G$ and $w(M') > w(M)$.

Is the hypothesis correct? If not, why is it wrong? What about the hypothesis with respect to non-bipartite graphs? If the hypothesis is correct, why is always Egervary's Theorem used?