Every Factor-Critical graph is bridgeless.

Question

Prove that every factor-critical graph is bridgeless.

I can't get the definition or any results that relate these two concepts, any hint is appreciated. Thanks

Answer 1

Definitions: A graph $G$ is said to be factor-critical if $\forall v \in V(G)$, $G-v$ has a perfect matching ( believe hypomatchable is another term used.) Note $G$ is necessarily of odd order. (By order I mean $|V(G)|$)

A graph $G$ is said to be bridgeless if it has no cut edge. In other words, the removal of any one edge will not result in an increase in the number of components of $G$.

Now to the statement at hand:

If $G$ is a factor-critical graph then $G$ is bridgeless.

Proof: Let $G$ be a factor critical graph. Suppose $G$ is not bridgeless, i.e. $G$ has a cut edge $e=uv$. Note that $G$ is necessarily of odd order. We remove $e$ to obtain $G' = G-e$, where $G'$ has two components $H_1$ of odd order and $H_2$ of even order (since odd $=$ odd $+$ even.) Now we have (WLOG) $u \in H_1$ and $v \in H_2$.

Can you find the contradiction?

The removal of $v$ gives a graph $G'' = G-v$ with $H_1$, an odd component, and some other components. But since $G''$ has an odd component, it cannot have a perfect matching, contradicting our factor-critical assumption.