A graph is called to be factor-critical if $G-v$ has a perfect matching for any vertex $v$ of $G$. Prove that a bipartite graph is never factor-critical.
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
Let's suppose that $G$ is bipartite, then I guess just let its two color classes consist of $m$ and $n$ vertices with the property such that $m\leq n$.
There's no way we can omit any vertex from the color class that's with $m$ elements so that resulting graph has a perfect matching.
$\therefore$We would get a bipartite graph with two color classes of different size.