Proof of Gallai Theorem for factor critical graphs

A remark: if $M$ and $N$ are matchings of maximal size, the components of the subgraph formed by the edges in $M\cup N$ are even cycles and paths of even length.

The following is due to de Caen.

Lemma: Suppose $u$ and $v$ are vertices in the graph $X$ such that any maximum matching covers at least one of them. If $M_u$ is a maximum matching in $X$ that misses $u$ and $M_v$ is a maximum matching which misses $v$, there is a path of even length in $M_u\oplus M_v$ with $u$ and $v$ as its end-vertices.

Proof: Let $H$ be the subgraph formed by the edges in $M_u\oplus M_v$. The components of $H$ are even cycles and paths and, as both $M_u$ and $M_v$ have maximum size, each path must have even length.

Our hypothesis implies that $u$ is covered by $M_v$ and $v$ is covered by $M_u$. Hence $u$ and $v$ have valency one in $H$ and therefore they are end-vertices of paths.

Suppose first that they lie on distinct paths and let $P$ be the path containing $u$. Then $P$ is an $M_v$-alternating path with even length and $M_v\oplus E(P)$ is a maximum matching which misses both $u$ and $v$.

But no maximum matching misses both $u$ and $v$, therefore $u$ and $v$must be end-vertices of the same path from $H$. As all paths in $H$ have even length, we are finished.

Lemma: Let $u$, $v$ and $x$ be distinct avoidable vertices in $G$.
If no maximum matching in $G$ misses both $u$ and $x$, and no maximum matching misses both $x$ and $v$, then no maximal matching misses both $u$ and $v$.

Proof: Let $M_x$ be a maximum matching that misses $x$ and suppose that $N$ is a maximum matching that misses both $u$ and $v$. By de Caen's lemma applied to $u$ and $x$, there is an alternating path in $M_x\cup N$ joining $u$ to $x$. By the same argument applied to $x$ and $v$, there is an alternating path from $x$ to $v$ in $M_x\cup N$. Since there can be only one alternating path in $M_x\cup N$ starting at $x$, this implies that $u=v$, a contradiction. Therefore there is no maximum matching in $G$ that misses $u$ and $v$.

Lemma (Gallai): If $X$ is connected and each vertex is missed by a maximum matching, then for each vertex $v$ the graph $X\setminus v$ has a perfect matching.

Proof: As $X$ is connected and all vertices are avoidable, from the previous lemma and a simple induction argument, we see that no two vertices of $G$ are missed by a maximum matching. Therefore each maximum matching of $G$ misses exactly one vertex.