The graph in your first question has no perfect matching. Since there are only $3$ vertices in $P_1$, a matching using all of those vertices can use at most $3$ of the $7$ vertices of $P_2$ and therefore cannot use all of them.
The two definitions are indeed of two different things. A perfect matching exhausts all of the vertices, so a bipartite graph that has a perfect matching must have the same number of vertices in each part. Deo is defining a directional notion: a complete matching from one part into the other. If $P_1$ and $P_2$ are the parts of a bipartite graph, $P_1$ had $m$ vertices, and $P_2$ has $n$ vertices, then a complete matching of $P_1$ into $P_2$ has $m$ edges, and a complete matching of $P_2$ into $P_1$ has $n$ edges. Thus, the former is possible only if $m\le n$, the latter is possible only if $n\le m$, and a perfect matching (which is automatically a complete matching of $P_1$ into $P_2$ and a complete matching of $P_2$ into $P_1$) is possible only if $m=n$.
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 matching in (b) is maximum: in a bipartite graph with partitions $X$ and $Y$ the number of edges in a maximum matching is at most $\min(|X|,|Y|)$. Here this last expression works out to 5, and five edges are used.
The matching in (b) is not complete because the planning job is not included in the assignment. Indeed, any graph with an odd number of vertices, like the one here with 11, has no complete matching. This term is rather old, with perfect matching being more common nowadays.