I am following the proof of Tutte-Berge formula here: https://homepages.cwi.nl/~lex/files/tutteb.pdf
In particular in the second half of the proof
I have 2 questions
- How does a matching of size $\frac{1}{2}(|V| - 1)$ imply the theorem taking $ U := \emptyset$ ? For this to hold true, the number of odd components $G$, denoted as $o(G)$ must be equal to 1. How is that immediate? Couldn't it as well be 0 ($G$ has only even components) or $>1$ ($G$ has multiple odd components)?
- At the last step of the proof, we claim that replacing N by $(N \setminus \{f\})\cup \{e\}$ increases the intersection with M. However, doing this replace means that some $w \in f = wy \in N$ gets removed from $N$. Are we assuming that $w \notin M$ or that eventually with successive replacements, we will end up removing some $w' \notin M$?
For the first question, suppose there is a matching of size $\frac12(|V|-1)$: covering all vertices except some vertex $x$.
A connected component cannot contain just half of an edge of this matching: if it contains one endpoint, it contains the other.
Since only one connected component contains $x$, there is only one odd component.
For the second question: certainly $w \notin M$, but maybe it is more accurate to say that it doesn't make sense to ask whether $w\in M$. The matching $M$ is a set of edges, and $w$ is a vertex.
The important thing to check here is that $(N \setminus \{f\}) \cup \{e\}$ is a matching. $(N \setminus \{f\})$ is a matching that does not cover $x$ (since $N$ did not) or $y$ (since $y$ was covered by $f$), so adding edge $e = xy$ gives us another matching.
From there, the reason that $|M \cap N|$ increases is that we remove an edge $f \notin M$, and add an edge $e \in M$. (We know $f \notin M$ because $e \in M$, and $f$ and $e$ share a vertex: two edges in a matching cannot share a vertex.)