An alternating path is not required to include all edges of a matching.
This causes no contradiction in the theorem you're citing: given a matching
and an augmenting path, you can always create a matching with more edges.
The simplest case is when the augmenting path is an edge that joins two vertices, neither covered by an edge of the matching, when you can just add the the extra edge (of the augmenting path).
First, $M= M \oplus C$ means that we add all edges in $C$ to $M$, and if any edge is in $C$ and old $M$, we remove it from $M$.
For $(1)$, induction is a fine approach. The key observation is that an augmenting path $C$ can 'undo' all previous edge choices, provided we keep the same matched nodes. Fortunately this is always the case.
Suppose for some maximum weight matching with $k$ edges $M_k$ with total weight $w_k$ there is a maximum weight matching with $k+1$ edges with some edge that is disjoint from the matched vertexes of $M_k$. Then there exists $k+1$ edges $e_i$ such that:
- $e_{k+1} = (u,v) \not \in M_k$ and further $u,v$ are unmatched by
$M_k$ (by assumption)
- $w_k \geq (\sum_i w(e_i) ) - e_{k+1} \implies w_k + w(e_{k+1}) \geq \sum_i w(e_i)$ (first part follows from $M_k$ being maximal with $k$ edges)
Note that $C = \{e_{k+1} \}$ would be a valid augmenting path, giving a matching with $k+1$ edges. This is because $e_{k+1}$ is disjoint from $M_k$.
Meanwhile, suppose there is a maximum weight matching $M'_{k+1}$ with $k+1$ edges that has no disjoint edges from $M_k$. Then we can follow a path from the first new vertex, alternating between edges in $M_k$ and the edges in $ M'_{k+1}$ (and skipping edges both share). Because they are both matchings, and they share matched vertecies, every matched vertex in $M_k$ has an edge from $M'_k$ and from $M_k$. If this happens to be the same edge, the agumenting path need not go through this node. If they are different, then that node can be part of an augmenting path coming in/out from one and out the other (hence alternating being in $M$ and out of $M$). Further, if they are not the same then the vertexes they connect to must also be matched differently by $M_k$ and $M'_k$ (otherwise some node would be matched twice). Therefore these nodes with different matchings in $M$ and $M'$ form a path, and since $M'_k$ is maximal, this path will be a minimal augmenting path.
Thus in either case, be there a maximum matching on $k+1$ edges that is disjoint or overlapping, we can find an augmenting path that will make $M$ do just as good.
For $(2)$, one way to find an augmenting path is via Bellman Ford, which takes $O(|V||E|) = O(n^3)$ time (Assuming one has the maximum of $O(n^2)$ edges). Naively you would have to run bellman from every start node, but you can modify the graph so that Bellman ford finds the shortest augmenting path with only one call. The trick is to modify the graph slightly before giving it to the algorithm. We add 2 new vertexes $s,t$, with $s$ connected to one bipartition by edges with weight $0$, and $t$ connected to the other. You then just need to find the minimal path from $s$ to $t$, which bellman ford does.
This only adds a linear number of edges and a constant number of vertecies, so the asymptotic runtime is not changed. Check how many calls we need to Bellman Ford (or your favorite $O(n^3)$ shortest paths algorithm), and we're done.
Best Answer
The algorithm you're looking for is called the Hungarian Maximum Matching Algorithm, and it works for any bipartite graph, for which it always gives the largest-size matching. More detailed info can be found on this Wolfram MathWorld page and this link has a neat visualisation of how the algorithm works.