Proof of Gallai Theorem for factor critical graphs

Question

I am trying to find the proof of the following theorem:

Definition 1.2. A vertex $v$ is essential if every maximum matching of $G$ covers $v$ (or $\nu(G-v) = \nu(G)-1$). It is avoidable if some maximum matching of $G$ exposes $v$ (or $\nu(G-v) = \nu(G)$). A graph $G$ is factor-critical if $G-v$ has a perfect matching for any $v \in V(G)$.

Theorem 1.3. Let $G$ be a connected graph. Then $G$ is factor-critical if and only if every vertex is avoidable.

I don't think this is something I can prove on my own. However, I can't seem to find the proof of it online either.

It makes sense intuitively. If for every vertex $v$, in graph $G$, there exists a perfect matching that doesn't include $v$, then removing $v$ and its incident edges would result in a perfect matching because one existed that didn't include $v$ in the first place.

Could someone provide a more formal proof for this theorem, or provide a link to where I might find the proof?

Thank You

Answer 1

First, suppose that $G$ is factor-critical. By definition, this means that for any vertex $v$ the subgraph $G-v$ has a perfect matching. Let's call that matching $M$. Since $M$ is perfect in $G-v$, it must be maximal in $G$, implying that $v$ is avoidable. Thus, every vertex in $G$ is avoidable.

Now, suppose that every vertex of $G$ is avoidable. This implies that for any pair of vertices, there is no maximum matching that misses both of them. Therefore, any maximum matching must only miss one particular vertex. Let's call that vertex $u$. This implies that $G-u$ has a perfect matching, and hence is factor-critical. Since every vertex is avoidable, this argument holds for every vertex in $G$. This implies that $G$ is factor-critical.

Answer 2

We prove the following:

THM: Let $G$ be a connected graph where for each vertex $v \in G$ there is a maximum matching that does not contain $v$. Then $G \setminus \{v\}$ has a perfect matching for each $v \in V(G)$.

First of all, the graph must be connected for this to be true. Indeed, 2 vertex-disjoint copies of a graph where all vertices are avoidable also has this property, and the maximum matching leaves at least 2 vertices uncovered. Secondly, this seems challenging to prove. I apologize for the length, I don't know how to make this any shorter.

We make the following claims:

Claim 1: Let $M^*$ be any maximum matching. Then for any vertex $v$ matched by $M^*$ at most 1 of $v$'s neighbors are not matched by $M^*$.

Proof of Claim 1: Let us suppose that there is a vertex $v$ and a matching $M^*$ not covering at least 2 of $v$'s neighbours which we write as $u_1$, $u_2$. Then let $M^*_v$ be a maximum-cardinality matching not covering $v$. Then $|M^*_v|=|M^*|$ Then as $M^*_v$ and $M^*$ are both maximum matchings and $v$ is covered by $M^*$ but not by $M^*_v$, the component $P$ of $M^*_v \cup M^*$ that contains $v$ is a path with (i) one of its endpoints $v$, and (ii) $|P \cap M^*| = |P \cap M^*_v|$. Furthermore, each of $u_1,u_2$ is also the endpoint of a path [or is an isolated vertex] of a component of $M^*_v \cup M^*$. So at least one of $u_1,u_2$, say $u_1$, is not in $P$ with $v$. So let $M'_v$ be the set of edges where

(a) $M'_v \cap P$ is the $|M^*_v \cap P|$ edges of $M^*_v \cap P$, plus

(b) $M'_v \setminus P^*$ is the set of $|M^*|-|M^* \cap P|$ $=$ $|M^*|-|M^*_v \cap P|$ edges of $M^*$ that are not in $P$.

Then $|M'_v|=|M^*|$ and leaves exposed both $v$ and $u_1$. Thus $M'_v + \{u_1v\}$ is a matching with cardinality strictly larger than $M^*$, contradicting that $M^*$ is a maximum matching. So Claim 1 follows. $\surd$

---

Now let $v$ be a vertex covered by $M^*$. We now define an $(v,M^*)$-alternating path to be a path $P$ where

(i) one endpoint of $P$ is $v$,

(ii) the edge in $P$ incident to $v$ is not in $M^*$, and

(iii) every alternating edge in $P$ is in $M^*$ [so the edge in $P$ incident to $v$ is not in $M^*$, but the next edge is in $M^*$, but the edge after that is not in $M^*$, and so on and so forth].

---

Claim 2: Let $v$ be a vertex matched by $M^*$. Then for some vertex $y(v)$ not covered by $M^*$ there is a $(v,M^*)$-alternating path from $v$ to $M^*$.

Proof of Claim 2: Let $M^*_v$ be a maximum matching that leaves $v$ uncovered. Then the component $P$ of $M^*_v \cap M^*$ is a path with one endpoint $v$. As $M^*_v$ has the same cardinality as $M^*$ and does not contain the edge in $M^*$ covering $v$ it follows that alternating edges of $P$ are in $M^*$ that the other endpoint of $P$ is not covered by $M^*$. $\surd$

Claim 3: Let $M^*$ be a maximum matching in $G$. For each $v$ matched by $M^*$ there is exactly one vertex $y(v)$ not matched by $M^*$ there is a $(v,M^*)$-alternating path with one endpoint in $v$ and the other endpoint in $y(v)$.

Proof of Claim 3: Let us suppose otherwise. Let $P_1$ be a $(v,M^*)$-alternating path where the other endpoint is in $y_1$; where $y_1$ not covered by $M^*$; a path $P_1$ exists by Claim 2. And let $P_2$ be a $(v,M^*)$-alternating path where the other endpoint is in $y_2$; where $y_2$ not covered by $M^*$. Let us assume that $P_1$ and $P_2$ do not intersect except at $v$. [Otherwise there is a vertex $v'$ on $P_1 \cap P_2$ that is covered by $M^*$ so that there is a $(v',M^*)$-alternating path $P'_1$ where the other endpoint is in $y_1$, and a $(v',M^*)$-alternating path $P'_2$ where the other endpoint is in $y_2$, and $P'_1$ and $P'_2$ intersect only at $v'$. Namely $P'_1$ is $P_1$ from $v'$ to $y_1$ and $P'_2$ is $P_2$ from $v'$ to $y_2$.]

Then let $M'$ be the matching formed from $M^*$ where (i) the edges in $M^* \cap P_1$ are replaced by those in $P_1 \setminus M^*$ except for the one edge in $P_1$ incident to $v$, and (ii) the edges in $M^* \cap P_2$ are replaced by those in $P_2 \setminus M^*$ except for the one edge in $P_2$ incident to $v$. Then because $P_1$ and $P_2$ intersect only at $v$, it follows that $M'$ is indeed a matching and has as many edges as $M^*$ so $|M'| \ge |M^*|$; and furthermore $v$ is still covered by $M'$. Also, 2 of $v$'s neighbours $u_1$ and $u_2$ [namely $u_1$ is $v$'s neighbor on $P_1$ and $u_2$ is $v$'s neighbour on $P_2$] are not covered by $M'$. So finish by Claim 1. $\surd$

Claim 4: Let $uv$ be an edge in $M^*$. Then $y(v)=y(u)$.

Proof of Claim 4: Let $P_1$ be a $(u,M^*)$-alternating path that ends in $y_1$; where $y_1$ not covered by $M^*$, and let $P_2$ be a $(v,M^*)$-alternating path that ends in $y_2$; where $y_2$ not covered by $M^*$; and $y_1 \not = y_2$. If $P_1$ and $P_2$ intersect then there exists a $(v,M^*)$ path from $v$ to both $y_1$ and $y_2$; finish as in the proof of Claim 3.

If $P_1$ and $P_2$ do not intersect then $P=P_1 \cup \{uy\} \cup P_2$ is a path where alternating edges in $P$ are in $M^*$ and where the endpoints of $P$ are not covered by $M^*$. So the matching $M'$ formed from $M^*$ by replacing the edges in $P \cap M^*$ with those in $P \setminus M^*$ is indeed a matching and has one more edge than $M^*$ does. $\surd$

---

We now finish the proof by showing that $M^*$ leaves only 1 vertex uncovered. Let us suppose that there are at least 2 unmatched vertices $y_1$ and $y_2$ be $M^*$. Then as $G$ is connected, let $P$ be a path where one endpoing is an unmatched vertex $y_1$ and the other endpoint is another unmatched vertex $y_2$ and where every other vertex is matched by $M^*$. Now write $P=y_1v_1\ldots v_ry_2$ where $v_1,\ldots, v_r$ are covered by $M^*$. Then defining $y(v)$ as in Claim 3, we note the following: $y(v_r)=y_2$ and $y(v_1)=y_1$ and each vertex $v_i$ has exactly one such $y(v_i)$ by Claim 2 so there exists an $i$ such that $y_1=y(v_i) \not = y(v_{i+1})=y_2$ So let $P_{i}$ be a $(v_i,M^*)$-alternating path from $v_i$ to $y_1$ and let $P_{i+1}$ be a $(v_{i+1},M^*)$-alternating path from $v_{i+1}$ to $y_2$.

If $v_iv_{i+1}$ is in $M^*$, then finish as in Claim 4.

If $v_iv_{i+1}$ is not in $M^*$ then writing as $u_{i+1}v_{i+1}$ be the edge in $M^*$ incident to $v_{i+1}$, by Claim 4 it follows that $y(u_{i+1})=y(v_{i+1})=y_2$. But then it follows that there is a $(v_i,M^*)$-alternating path $P$ from $v_i$ to $y_2$ as well as $y_1$; namely the first two edgres in $P$ are $v_iv_{i+1}$ and $v_{i+1}u_{i+1}$. So finish via Claim 3.

Thus $M^*$ indeed leaves only 1 vertex unmatched, and as we are given that for each vertex $v$ there is a matching $M^*_v$ that does not cover $v$ and that satisfies $|M^*|=|M^*_v|$, the theorem follows. $\surd$

Answer 3

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.

Answer 4

This can be proved quickly using the Tutte-Berge formula. For a subset of vertices $U \subseteq V$, let $q(U)$ denote the number of odd components of $G - U$. The Tutte-Berge formula states, in effect, that there is some $U \subseteq V$ such that a maximum size matching of $G$ avoids exactly $q(U) - |U|$ vertices. Now it is easy to see that any matching of $G$ avoids at least $q(U) - |U|$ vertices of $G-U$: from each of the $q(U)$ odd components at least one vertex must be either unmatched or matched to a vertex in $U$, and the latter can happen for at most $|U|$ vertices. It follows that the vertices in $U$ are not avoidable, so by assumption $U$ must be empty. Then, since $G$ is connected, $q(U) - |U| = q(U)$ is either $0$ or $1$. The former would mean that $G$ has a perfect matching, so that none of the vertices are avoidable, a contradiction. So every maximum matching avoids exactly one vertex, which, together with the assumption that every vertex is avoidable, implies that $G$ is factor-critical.

In general, the behaviour of the set of avoidable vertices is described by the so-called Edmonds-Gallai decomposition of the graph, see e.g. Theorem 2 of these lecture notes. Gallai's Theorem immediately follows from this decomposition.